Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### MedoN11's blog

By MedoN11, 9 years ago,

Link to my solution : https://ideone.com/4rRdS9

I'm basically precomputing the input, and for each cell that lies in x-d<=i && y-d<=j, I'll add it's cost to killed[i][j].

It's a classical problem, if there is anything that's not clear within my code. I'm willing to provide a more detailed explanation.

I estimated the complexity to be N*d^2. Isn't that ok enough for 3 seconds?

Thanks.

• +7

 » 9 years ago, # | ← Rev. 4 →   0 I am sorry. It's fast enough.
•  » » 9 years ago, # ^ |   0 It's fast, but you are right that it can be solved with O(Size^2) that would be better because it would be independent from maximum of "d"-value.All you need to calculate sum[i][j] — prefix sum of all rats on area [1..i, 1..j] (it can be calculated in O(Size^2)). After that sum of some area [x1..x2][y1..y2] can be easily calculated in O(1).
•  » » 9 years ago, # ^ |   0 Still, thanks for putting your time to help me. ;)
 » 9 years ago, # |   +1 I'm not sure, but it seems that you have bug in this line:  for(int k=y-d;j<=k+d;k++){ I think that it should be like  for(int k=y-d;k<=y+d;k++){ 
•  » » 9 years ago, # ^ |   0 Thanks a lot. It was a stupid typo from my part. Got AC :).