AT_dp_z.Frog 3

有 $N$ 个台阶。每个台阶编号为 $1, 2, \ldots, N$。对于每个 $i$（$1 \leq i \leq N$），第 $i$ 个台阶的高度为 $h_i$。已知 $h_1 < h_2 < \cdots < h_N$。

一只青蛙最初在台阶 $1$ 上。青蛙可以多次进行如下操作，试图到达台阶 $N$：

• 当青蛙在台阶 $i$ 时，可以跳到台阶 $i+1, i+2, \ldots, N$ 中的任意一个。若跳到台阶 $j$，则需要支付的代价为 $(h_j - h_i)^2 + C$。

请你求出青蛙到达台阶 $N$ 所需支付的总代价的最小值。

输入以如下格式从标准输入给出。

$N$ $C$ $h_1$ $h_2$ $\ldots$ $h_N$

输出青蛙所需支付的总代价的最小值。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq C \leq 10^{12}$
• $1 \leq h_1 < h_2 < \cdots < h_N \leq 10^6$

样例解释 1

若青蛙依次跳到台阶 $1 \to 3 \to 5$，总代价为 $((3-1)^2 + 6) + ((5-3)^2 + 6) = 20$。

样例解释 2

答案可能超出 32 位整数范围。

样例解释 3

若青蛙依次跳到台阶 $1 \to 2 \to 4 \to 5 \to 8$，总代价为 $((3-1)^2 + 5) + ((5-3)^2 + 5) + ((10-5)^2 + 5) + ((13-10)^2 + 5) = 62$。

由 ChatGPT 4.1 翻译