Hello guys :)

Today I tried to solve IOI 2015's first problem (Boxes with Souvenirs). I thought of dynamic programming:

dp[i] = min(dp[j] + min(l, 2 * (l - pos[j + 1]), 2 * pos[i]) ( j >= i — k and j < i)

So this algo is O(N^2) and it time limit. My question is how to reduce it to O(N).

Thanks in advance :)