765 Div. 2, Solved #C. with simple idea but need help

In the worst case, size of your vector will still be 500*500*500.

Instead convert this code to iterative dp and then you can reduce the space ( since in transition for n you are only going to n+1, so for state n only previous States are required)

Here is the recursive solution similar to yours https://codeforces.net/contest/1625/submission/142496055

After that I converted this to iterative dp but still using all 3 states https://codeforces.net/contest/1625/submission/142510147

Here is my accepted solution using the idea described above ( removing redundant space for state n) https://codeforces.net/contest/1625/submission/142512319

During contest I also did with the exactly same approach and got MLE. But after removing last variable and using a loop instead of that I got accepted using recursion + memoization. Here is my code 142546595. Hope this would help. You can ask if you feel any difficulty in understanding :)