Căn Lề Đoạn Văn Tối Ưu
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Một đoạn văn gồm $N$ từ có độ dài lần lượt là $w_1, w_2, \dots, w_N$. Mỗi dòng có độ rộng tối đa là $M$. Khi xếp các từ từ $l$ đến $r$ trên cùng một dòng (giữa hai từ liên tiếp có đúng 1 dấu cách), tổng độ dài chiếm dụng là: \[\text{len}(l, r) = (r - l) + \sum_{i=l}^r w_i\] Nếu $\text{len}(l, r) \le M$, chi phí của dòng đó là $(M - \text{len}(l, r))^3$; ngược lại dòng đó không hợp lệ. Hãy tìm tổng chi phí nhỏ nhất để xếp toàn bộ $N$ từ thành các dòng hợp lệ (tất cả các dòng đều tính chi phí, kể cả dòng cuối).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \le N \le 10^5, 1 \le M \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $w_1, w_2, \dots, w_N$ ($1 \le w_i \le M$).
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 6 3 2 2 5 |
29 |
| 3 5 2 2 2 |
27 |
Giới hạn
- $1 \le N \le 10^5$
- $1 \le w_i \le M \le 10^5$
Community Discussion