### ApaarGulati's blog

By ApaarGulati, history, 2 weeks ago,

Hi. i am a beginner in CP. i know only python. is there a way of solving 1994C - Голодные игры, without using dynamic programming? i tried to make subsegments and iterating through each one but i am getting TLE at test cases 5.

my submission:271274872

please suggest if there is any alternate approach this other than using dp.

Thanks

• 0

 » 2 weeks ago, # | ← Rev. 7 →   0 Check the following accepted Python code based on the dynamic programming algorithm described in the editorial. Python version of the editorial solutionfrom bisect import bisect_right from itertools import accumulate def next_line(): return input() def next_int(): return int(next_line()) def next_imap(): return map(int,next_line().split()) def solve(n,x,partial_sum): dp = [0]*(2*(n+1)) ans = 0 for i in range(n-1,-1,-1): j = bisect_right(partial_sum,partial_sum[i]+x)-1 dp[i] = dp[j+1]+j-i ans += dp[i] return ans for test_case in range(next_int()): n, x = next_imap() print(solve(n,x,[0]+list(accumulate(next_imap())))) 
•  » » 2 weeks ago, # ^ |   0 Thank you!
•  » » » 2 weeks ago, # ^ |   0 With pleasure. Check the slight update to the accepted Python code in the previous reply.