link to problem : http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1301

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.

I am sorry. It's fast enough.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).

Still, thanks for putting your time to help me. ;)

I'm not sure, but it seems that you have bug in this line:

I think that it should be like

Thanks a lot. It was a stupid typo from my part. Got AC :).