← 返回题目列表

AtCoder · dp_z

Z. 青蛙 3

中文机器翻译题面 查看原题

分数: 100 点

问题陈述

有 N 石头,编号 1, 2, \ldots, N。 对于每个 i (1 \leq i \leq N), 石头的高度 i is h_i。 在这里, h_1 < h_2 < \cdots < h_N 成立。

有一只青蛙最初在石头上 1。 他会重复以下动作多次才能到达斯通 N:

  • 如果青蛙当前位于石头上 i,跳转到以下选项之一:Stone i + 1, i + 2, \ldots, N。这里,成本为 (h_j - h_i)^2 + C 正在开始,其中 j 是着陆的石头。

找出青蛙到达石头之前开始的最小可能总成本 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

输入

输入由标准输入按以下格式给出:

N C
h_1 h_2 \ldots h_N

输出

打印可能产生的最小总成本。


示例输入 1

5 6
1 2 3 4 5

示例输出 1

20

如果我们沿着这条路走 1 → 3 → 5,总成本将开始 ((3 - 1)^2 + 6) + ((5 - 3)^2 + 6) = 20.


示例输入 2

2 1000000000000
500000 1000000

示例输出 2

1250000000000

答案可能不适合 32 位整数类型。


示例输入 3

8 5
1 3 4 5 10 11 12 13

示例输出 3

62

如果我们沿着这条路走 1 → 2 → 4 → 5 → 8,总成本将开始 ((3 - 1)^2 + 5) + ((5 - 3)^2 + 5) + ((10 - 5)^2 + 5) + ((13 - 10)^2 + 5) = 62.