Đóng Gói Liên Tiếp
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ món đồ xếp theo thứ tự từ $1$ đến $N$, món đồ thứ $i$ có kích thước $a_i$. Bạn muốn chia $N$ món đồ này thành một số lượng tùy ý các thùng hàng liên tiếp. Chi phí để đóng gói một thùng chứa các món đồ từ $l$ đến $r$ là: \[w(l, r) = \left(L - \sum_{i=l}^r a_i\right)^2\] trong đó $L$ là kích thước chuẩn của mỗi thùng. Lưu ý tổng kích thước các món đồ trong một thùng có thể lớn hơn, bằng hoặc nhỏ hơn $L$. Hãy tìm tổng chi phí đóng gói nhỏ nhất có thể.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $L$ ($1 \le N \le 10^5, 1 \le L \le 10^9$).
- Dòng thứ hai chứa $N$ số nguyên $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 2 3 4 1 |
0 |
| 3 10 4 4 4 |
4 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le L \le 10^9$
- $1 \le a_i \le 10^4$
Community Discussion