Блог пользователя MedoN11

Автор MedoN11, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I am sorry. It's fast enough.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 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).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +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++){