Phân bổ công việc theo dãy
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
recursion
Đề bài
Có $N$ gói hàng xếp thành một hàng, gói thứ $i$ có khối lượng $a_i$. Cần phân chia dãy $N$ gói hàng này cho $K$ xe tải sao cho mỗi xe chở một đoạn các gói hàng liên tiếp nhau, và mỗi gói hàng thuộc đúng một xe (một xe có thể không chở gói nào nếu $K > N$). Hãy tìm giá trị nhỏ nhất có thể của tổng khối lượng lớn nhất mà một xe phải chở.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$.
Dữ liệu ra
- In ra một số nguyên duy nhất là kết quả tối ưu.
Ví dụ
| Dữ liệu vào | Dữ liệu ra |
|---|---|
| 5 3 2 4 7 3 5 |
8 |
Giới hạn
- $1 \le N, K \le 10^5$
- $1 \le a_i \le 10^9$
Community Discussion