Let \(dp_i\) be the minimum cost incurred in order to reach Stone \(i\). \(dp_i\) can be found in the recurrence relation as follows:

\(dp_i = \min\limits_{1 \le j \lt i}\bigl((h_i - h_j)^2 + C + dp_j\bigr)\)

Naïvely evaluating this formula takes \(O(N^2)\) time, which does not fit in the execution time limit. For now, we can move the terms not dependent on \(j\) out of \(\min\), so the relation above can be re-phrased as follows:

\(dp_i = \min\limits_{1 \le j \lt i}\bigl(-2h_ih_j+h_j^2+dp_j\bigr)+h_i^2+C\)

In the equation, the expression inside \(\min\) is a linear function in respect to \(h_i\), so we can use CHT (convex hull trick) to solve the problem. For each \(1 \le i \le N\), we can do the following:

1. Finding the value of \(dp_i\)
   • If \(i = 1\), let \(dp_1 = 0\).
   • Otherwise, let \(v\) be the value corresponding to \(x = h_i\) in the convex hull. We can find that \(dp_i = v + h_i^2 + C\).
2. Updating the convex hull
   • Insert the linear function \(y = -2h_ix + h_i^2 + dp_i\) into the convex hull.

By this algorithm, the problem can be solved in \(O(N \log N)\) time complexity, which easily fits in the time limit.