Chia Dãy Cân Bằng · canuc80k0508 · Thuật toán Canuc80k

Cho dãy $n$ số nguyên dương. Hãy đặt $k - 1$ đường cắt để chia dãy thành đúng $k$ đoạn liên tiếp, không rỗng và phủ toàn bộ dãy.

Giá của một cách chia là tổng lớn nhất trong số $k$ đoạn. Hãy tìm giá nhỏ nhất có thể của giá này.

Input

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_{1}, \dots, a_{n}$ .

Output

In giá nhỏ nhất có thể của tổng đoạn lớn nhất.

Constraints

$1 \leq k \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq a_{i} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50$ điểm): $n \leq 5000$ .
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

7 3
4 2 7 3 5 1 6

Output

Giải thích: Cách chia $[4, 2], [7, 3], [5, 1, 6]$ có tổng lớn nhất bằng $12$ ; với giới hạn $11$ , phép quét tham lam cần bốn đoạn nên không thể chia thành ba đoạn.

Ý tưởng: Giả sử giới hạn tổng mỗi đoạn là M. Vì các phần tử dương, cách quét tham lam - kéo dài đoạn hiện tại tối đa rồi mới cắt - dùng số đoạn ít nhất có thể dưới giới hạn M. Giới hạn khả thi khi số đoạn đó không vượt k; nếu dùng ít hơn k, có thể tách thêm tại các vị trí vì mọi phần tử dương và k≤n.
Ý tưởng: Tính khả thi không giảm theo M, nên chặt nhị phân giá trị nhỏ nhất trong đoạn từ max(a_i) đến Σa_i.
Ý tưởng: Tính đúng đắn: greedy tối thiểu hóa số đoạn cho một M; do đó parts≤k tương đương tồn tại cách chia đúng k đoạn. First true của điều kiện này chính là giá nhỏ nhất cần tìm.
Ý tưởng: Độ phức tạp là O(n log Σa_i) thời gian và O(n) bộ nhớ.