Getting TLE even with memoization

Code: https://codeforces.com/contest/909/submission/55870468
Problem: https://codeforces.com/contest/909/problem/C
I’ve used memoization but still I get TLE in this problem

edit: okay i get it the complexity is not n**2, how do i fix this?

Keep track of the prefix sum.
Instead of calculating it over and over again.

1 Like

Yes! I can’t figure it out how to do It with 2D, can you tell…?

When going over all possible indentations of a statement,i,why not sum up the values of these states and store them in an array sum.
Where sum[j] = summation of all counts(state values) for all indentations j and above for the ith statement.
Then for the ( i+1 )th statement,you can simply do dp[i][j] = sum[j] when applicable

1 Like

But there are different Indent levels, so won’t I need 2d array?
sum[i][j]= sum till i when indent is j = sum[i-1][j]+dp[i][j] ?

At each new statement,you only need the sum array(indent sums) of the previous statement,not of the ones before that.
sum[] should inherently imply indent sums of the (i-1)th statement when processing the ith statement.
Then you can continue to reuse this sum array.

1 Like

Can you help me implement it? I can’t figure it out:
https://codeforces.com/contest/909/submission/55870468