Codeforces 674C Levels and Regions - Standard DP

Standard DP: $dp[i][j]$ = minimum expected time to complete first $i$ levels using exactly $j$ regions. Transition (the formula to compute each state): $dp[i][j] = \min_{p < i}(dp[p][j-1] + cost(p+1, i))$ where $cost(l, r)$ is the expected time to complete levels $l$ through $r$ as a single region.

Time complexity: $O(n^2 k)$.

Space complexity: $O(n)$ for the dp array. With $n = 200{,}000$ and $k = 50$, that's $2 \times 10^{12}$ operations. Way too slow. Even $O(n^2)$ transitions are borderline at $4 \times 10^{10}$ operations.