Phân chia công việc
Một nhóm thợ có \(n\) công việc cần làm, mỗi công việc mất một số giờ nhất định để hoàn thành. Công việc thứ \(i\) mất \(a_i\) giờ.
Bạn được yêu cầu chia các công việc này thành \(k\) đoạn liên tiếp (các công việc trong cùng một đoạn phải liền kề nhau). Mỗi đoạn sẽ được giao cho một người thợ.
Nhiệm vụ của bạn là chia sao cho thời gian làm việc lâu nhất trong số \(k\) thợ là nhỏ nhất có thể.
Input
Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) \((1 \leq k \leq n \leq 2 \times 10^5)\).
Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) --- thời gian cần để hoàn thành công việc thứ \(i\).
Output
In ra một số nguyên --- thời gian làm việc lâu nhất mà một người thợ phải thực hiện, nếu chia công việc theo cách tối ưu.
Example
Test 1
Input
5 3
2 4 7 3 5Output
8Note
Một cách chia tối ưu là \([2,4],[7],[3,5]\) trong đó tổng của các đoạn con là \(6,7,8\). Thời gian lâu nhất một người thợ phải hoàn thành là \(8\).
Scoring
- Subtask 1 (20 điểm): \(k = 2\)
- Subtask 2 (30 điểm): \(k = 3\)
- Subtask 3 (50 điểm): Không có ràng buộc gì thêm.