Atcoder Educational DP Contest Z - Frog 3
Xem dạng PDF
Gửi bài giải
Điểm:
1,45 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.