Chia kiện hàng vận chuyển

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm Buổi 08 — Contest Chặng 1
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved