Đóng Gói Lô Hàng

Buổi 37 — Convex Hull Trick Dynamic Programming
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề bài

Một nhà máy có $N$ kiện hàng xếp thành hàng ngang, kiện thứ $i$ có kích thước $a_i$. Nhà máy muốn chia $N$ kiện hàng này thành các lô liên tiếp để đóng gói.

Nếu một lô gồm các kiện hàng từ $j+1$ đến $i$ với tổng kích thước là $S = \sum_{k=j+1}^{i} a_k$, chi phí đóng gói lô đó là: \[(S - L)^2 + C\] trong đó $L$ là kích thước chuẩn và $C$ là chi phí cố định cho mỗi lô.

Hãy tìm tổng chi phí đóng gói nhỏ nhất để chia hết $N$ kiện hàng.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $N, L, C$ ($1 \le N \le 10^5$, $0 \le L \le 10^6$, $0 \le C \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 1000$).
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
2 3 4 1
4
Giới hạn
  • $1 \le N \le 10^5$
  • $1 \le a_i \le 1000$, $0 \le L \le 10^6$, $0 \le C \le 10^9$
Draft saved