K painters are assigned to paint a row of boards of different lengths, working in parallel, and Arif (also the event's part-time coordinator) wants to MINIMIZE the maximum work assigned to any single painter. Given N boards with lengths a_1..a_N and K painters, each painter paints a contiguous set of boards, and all painters work in parallel. Minimize the maximum total length painted by any single painter. Binary search on the answer (the max length), with a greedy feasibility check.
Input
Line1: N K. Line2: N integers.
Output
The minimized maximum length.
Constraints
1 ≤ K ≤ N ≤ 10^5
Sample Input
5 3 10 20 30 40 50
Sample Output
60
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.