Problem : https://mirror.codeforces.com/contest/1288/problem/C

My solution: https://mirror.codeforces.com/contest/1288/submission/68821660

Can anyone tell while I calculate dp[pos][i][j], I am using O(n*n) to calculate for each pair. Can I optimize by using some precalculated sum array, as we do in 1D case to get the sum for a particular range in an array?

In my code, I have written this, //to calculate dp[pos][i][j] //using dp[pos — 1][previ][prevj]

How can I do this in O(1) to fit in timelimit?

I am thinking about this optimization for a long time, but I got to nowhere.

It would be great if there is any way to do it.

Thank you :)

Have a great day!