Atcoder Educational DP Contest Z - Frog 3

View as PDF

Submit solution


Points: 1.45 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có ~N~ hòn đá được đánh số từ 1 tới ~N~. Hòn đá thứ ~i~ ~(1 \le i \le N)~ có chiều cao ~h_i~. Ngoài ra ta có ~h_1 < h_2 < ... < h_n~.

Có một chú ếch khởi đầu ở hòn đá thứ ~1~ và nó sẽ lặp lại các hành động như sau để đến được hòn đá thứ ~N~:

  • Nếu nó đang ở hòn đá ~i~, nó có thể nhảy đến bất kì hòn đá: ~i + 1, i + 2, ... N~ và mất chi phí là ~(h_j - h_i)^2 + C~ với ~j~ là hòn đá mà nó nhảy đến.

Hãy tìm chi phí nhỏ nhất có thể để chú ếch đến được hòn đá thứ ~N~.

Input

  • Dòng đầu chứa hai số nguyên ~N~ và ~C ~ lần lượt là số viên đá và hệ số chi phí.
  • Dòng tiếp theo chứa ~N~ số nguyên lần lượt là chiều cao của các hòn đá.

Giới hạn:

  • ~1 \leq N \leq 2 \times 10^5~
  • ~1 \leq C \leq 2 \times 10^{12}~
  • ~1 \leq h_1 < h_2 < ... < h_n \leq 10^6~

Output

Ghi ra chi phí nhỏ nhất có thể.

Sample 1

Input 1
5 6
1 2 3 4 5
Output 1
20

Nếu chú ếch nhảy lần lượt lên các hòn đá ~1 \rightarrow 3 \rightarrow 5~ thì chi phí sẽ là: ~((3-1) ^ 2 + 6) + ((5-3)^2 + 6) = 20~.

Sample 2

Input 2
2 1000000000000
500000 1000000
Output 2
1250000000000

Sample 3

Input 3
8 5
1 3 4 5 10 11 12 13
Output 3
62

Nếu chú ếch nhảy lần lượt lên các hòn đá ~1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 8~ thì chi phí sẽ là: ~((3-1) ^ 2 + 5) + ((5-3) ^ 2 + 5) + ((10-5) ^ 2 + 5) + ((13-10) ^ 2 + 5) = 62~.

Note

Kết quả có thể vượt quá kiểu số nguyên 32 bit.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.