Hi, I have written a simple dp solution for this problem ==> https://mirror.codeforces.com/contest/383/problem/D.
But its something strange that it gets accepted without memory optimizes ==> https://mirror.codeforces.com/contest/383/submission/68460051
and it doesnt get accepted with memory optimize ( Every state gets update only from before (i-1) So we can only have 2 rows). https://mirror.codeforces.com/contest/383/submission/68460038
The only thing that different is in these two solutions is simple memory optimizing.
UPD: solved