Phân bổ thợ sửa máy

Binary-search Buổi 13 — Chặt nhị phân đáp án
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Có $N$ chiếc máy đặt thành một hàng ngang, chiếc máy thứ $i$ cần $t_i$ phút để sửa chữa. Bạn có $K$ người thợ sửa máy. Mỗi người thợ chỉ có thể được giao một đoạn gồm các chiếc máy liên tiếp nhau, và mỗi chiếc máy phải được giao cho đúng một người thợ (một số người thợ có thể không được giao máy nào).

Các người thợ làm việc đồng thời. Hãy tìm thời gian hoàn thành sớm nhất (tức là giá trị lớn nhất của tổng thời gian làm việc của một người thợ là nhỏ nhất có thể).

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $K$ ($1 \le K \le N \le 10^5$).
  • Dòng thứ hai chứa $N$ số nguyên $t_1, t_2, \dots, t_N$ ($1 \le t_i \le 10^9$).
Dữ liệu ra
  • In ra một số nguyên duy nhất là thời gian hoàn thành sớm nhất.
Ví dụ
Input Output
5 3
10 20 30 40 50
60
Giới hạn
  • $1 \le K \le N \le 10^5$
  • $1 \le t_i \le 10^9$
Draft saved