Chia kiện hàng vận chuyển
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trên băng chuyền có $N$ kiện hàng xếp thành hàng ngang, kiện thứ $i$ có khối lượng $w_i$. Cần chia băng chuyền thành tối đa $K$ đoạn liên tiếp để chất lên $K$ xe tải (mỗi xe chở một đoạn liên tiếp các kiện hàng). Hãy tìm tải trọng nhỏ nhất có thể của chiếc xe phải chở nặng nhất.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, K$. Dòng thứ hai chứa $N$ số nguyên dương $w_1, w_2, \dots, w_N$.
Dữ liệu ra
Một số nguyên duy nhất là tải trọng tối thiểu tìm được.
Ví dụ
| Input | Output |
|---|---|
| 5 2 10 20 30 40 50 |
90 |
| 4 4 5 10 3 7 |
10 |
Giới hạn
- $1 \le K \le N \le 10^5$
- $1 \le w_i \le 10^9$
Community Discussion