cooldown's blog

467C Time limit exceeded on test 15
By cooldown, 9 years ago, In English

I am a bit confuse about this problem. I am not sure I understand the dp process correctly.

I define the state as dp[i][j], which means the max sums until the i-th position and j pairs. so,

dp[i][j] will update dp[i+m][j+1] (including numbers starting from i+1 to i+1+m)

dp[i+m+1][j+1](including numbers starting from i+2 to i+2+m)

....

But this solution exceed the time limit. I can't find where is the problem. could you please help me. thank you in advance.

here is my solution, link: http://codeforces.com/contest/467/submission/9970270

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Your solution runs in approx. n*n*k operations, which exceeds time limit.

The expected solution runs in n*k.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks, but according to my state transform process, I can't make it in n*k. Maybe the dp process I use is wrong, but i don't know why? I read others' codes and find that they use the same define of dp[i][j] as me, but they don't transform the state as i do. My brain stops......

    → Reply