Tuyến cáp quang tối ưu
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Có $N$ trạm phát sóng đặt trên một trục tọa độ tại các vị trí nguyên tăng dần $x_1 < x_2 < \dots < x_N$. Ta cần truyền tín hiệu từ trạm $1$ đến trạm $N$ bằng cách chọn một dãy các trạm trung chuyển $1 = i_1 < i_2 < \dots < i_k = N$.
Mỗi bước truyền tín hiệu trực tiếp từ trạm $i_t$ đến trạm $i_{t+1}$ tiêu tốn chi phí bằng $(x_{i_{t+1}} - x_{i_t})^2 + C$, trong đó $C$ là hằng số chi phí lắp đặt. Hãy tìm tổng chi phí nhỏ nhất để truyền tín hiệu từ trạm $1$ đến trạm $N$.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $C$ ($2 \le N \le 2 \cdot 10^5$, $0 \le C \le 10^{12}$).
- Dòng thứ hai chứa $N$ số nguyên $x_1, x_2, \dots, x_N$ ($0 \le x_1 < x_2 < \dots < x_N \le 10^6$).
Kết quả
- In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Subtasks
- Subtask 1 (25% số điểm): $N \le 2000$.
- Subtask 2 (25% số điểm): $C = 0$.
- Subtask 3 (50% số điểm): Không có ràng buộc bổ sung.
Ví dụ
| Input | Output |
|---|---|
| 4 10 1 3 6 10 |
59 |
Community Discussion