Đóng Gói Liên Tiếp

Binary-search Buổi 38 — Divide & Conquer DP Dynamic Programming
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved