Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

kznil96's blog

By kznil96, history, 6 weeks ago, In English,

Below is a code I wrote for Atcoder dynamic programming contest problem B. The result returns TLE for 3 out of 16 test cases.

Problem: link to problem

image of problem

Code (python):

image of my code

The approach is just standard DP, with complexity of N times K.

Based on me looking around, a lot of people have submitted similar solutions with accepted verdict.

Can anyone tell me why is it that the code above exceed time limit, and suggest improvements? (maybe it has to do with ways of reading input etc)

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

6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can define B as map(int, stdin.readline().split()), so you would not have to parse B[k-1] and B[k-j-1] multiple times in line 15.