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:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
This comment is hidden due to too much negative feedback. Show it anyway.