Thuê Máy Chủ Đám Mây
Points
65
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Một hệ thống cần xử lý $N$ tác vụ theo đúng thứ tự từ $1$ đến $N$. Tác vụ thứ $i$ có thời lượng $a_i > 0$.
Các tác vụ được gom thành các lô liên tiếp. Nếu một lô gồm các tác vụ có tổng thời lượng là $S$, chi phí xử lý lô đó là $S^2 + C$, trong đó $C$ là chi phí khởi tạo cố định cho mỗi lô. Hãy chia $N$ tác vụ thành một hoặc nhiều lô liên tiếp sao cho tổng chi phí xử lý tất cả các lô là nhỏ nhất.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $C$ ($1 \le N \le 10^5$, $0 \le C \le 10^{12}$).
- Dòng thứ hai chứa $N$ số nguyên dương $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 10^4$).
Dữ liệu ra
- Một số nguyên duy nhất là tổng chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 3 4 |
49 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le C \le 10^{12}$, $1 \le a_i \le 10^4$
Community Discussion