Codeforces 713C Sonya and Problem Without a Legend - Problem Statement

You have $n$ numbers. Change each to any value. The cost of changing $a_i$ to $x$ is $|x - a_i|$. Make the array strictly increasing with minimum total cost. Naive DP (dynamic programming): $dp[i][v]$ = min cost for first $i$ elements with $a_i = v$. Transition: $dp[i][v] = \min_{w < v} (dp[i-1][w] + |v - a_i|)$.

This is $O(n \cdot V^2)$. With $V = 10^9$, impossible. Think about the shape of $dp[i]$ as a function of the last value. It's piecewise linear and convex. You'll track slope changes instead of all values.