/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
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 に辿り着くまでに支払うコストの総和の最小値を求めてください。
制約
- 入力はすべて整数である。
- 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-bit 整数型に収まらない場合があります。
入力例 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 となります。
Score : 100 points
Problem Statement
There are N stones, numbered 1, 2, \ldots, N. For each i (1 \leq i \leq N), the height of Stone i is h_i. Here, h_1 < h_2 < \cdots < h_N holds.
There is a frog who is initially on Stone 1. He will repeat the following action some number of times to reach Stone N:
- If the frog is currently on Stone i, jump to one of the following: Stone i + 1, i + 2, \ldots, N. Here, a cost of (h_j - h_i)^2 + C is incurred, where j is the stone to land on.
Find the minimum possible total cost incurred before the frog reaches Stone N.
Constraints
- All values in input are integers.
- 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
Input
Input is given from Standard Input in the following format:
N C h_1 h_2 \ldots h_N
Output
Print the minimum possible total cost incurred.
Sample Input 1
5 6 1 2 3 4 5
Sample Output 1
20
If we follow the path 1 → 3 → 5, the total cost incurred would be ((3 - 1)^2 + 6) + ((5 - 3)^2 + 6) = 20.
Sample Input 2
2 1000000000000 500000 1000000
Sample Output 2
1250000000000
The answer may not fit into a 32-bit integer type.
Sample Input 3
8 5 1 3 4 5 10 11 12 13
Sample Output 3
62
If we follow the path 1 → 2 → 4 → 5 → 8, the total cost incurred would be ((3 - 1)^2 + 5) + ((5 - 3)^2 + 5) + ((10 - 5)^2 + 5) + ((13 - 10)^2 + 5) = 62.