Tuyến cáp quang tối ưu

Buổi 67-68 — Mock IOI Dynamic Programming
Points
100
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề 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
Draft saved