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:
Code (python):
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)
You can define B as
map(int, stdin.readline().split()), so you would not have to parseB[k-1]andB[k-j-1]multiple times in line 15.