Phân chia dãy số

Mã bài: binarysearch09 Nhóm: Uncategorized Dạng bài: Undefined

Giới hạn thời gian: 1,0 s
Giới hạn bộ nhớ: 256 MB
Điểm: 100
Tỉ lệ AC: 23,7%
Người giải: 8

Nguồn: CSES

Cho dãy số nguyên $a$ ~a~ độ dài $n$ ~n~ và một số nguyên dương $k$ ~k~. Nhiệm vụ của bạn hãy chia dãy $a$ ~a~ thành $k$ ~k~ dãy con liên tiếp sao cho tổng lớn nhất của một dãy con đạt giá trị càng nhỏ càng tốt.

Input

Dòng đầu tiên chứa hai số nguyên $n$ ~n~ và $k$ ~k~ $(1 \le k \le n \le 2.10^5)$ ~(1 \le k \le n \le 2.10^5)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên dãy $a$ ~a~ $(0 \le a_i \le 10^9)$ ~(0 \le a_i \le 10^9)~.

Output

In ra giá trị nhỏ nhất có thể của tổng lớn nhất của dãy con.

Samples

Sample Input 1

5 3
2 4 7 3 5

Sample Output 1

Clarification

Trong ví dụ, một cách chia tối ưu là $[2,4]$ ~[2,4]~, $[7]$ ~[7]~ và $[3,5]$ ~[3,5]~, tổng các dãy con tương ứng là $6$ ~6~, $7$ ~7~ và $8$ ~8~. Tổng lớn nhất của một dãy con là $8$ ~8~.

Scoring

Subtask $1$ ~1~ $(10\%)$ ~(10\%)~ số điểm: $k=1$ ~k=1~
Subtask $2$ ~2~ $(10\%)$ ~(10\%)~ số điểm: $k=n$ ~k=n~
Subtask $3$ ~3~ $(12\%)$ ~(12\%)~ số điểm: $k=2$ ~k=2~
Subtask $4$ ~4~ $(20\%)$ ~(20\%)~ số điểm: $a_i \le 1$ ~a_i \le 1~
Subtask $5$ ~5~ $(22\%)$ ~(22\%)~ số điểm: $n \le 100,$ ~n \le 100,~ $a_i \le 1000$ ~a_i \le 1000~
Subtask $6$ ~6~ $(26\%)$ ~(26\%)~ số điểm: Không còn ràng buộc gì thêm