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 :).