A river dock must ship n cargo units downstream using one barge. The units sit in a fixed loading queue and must be shipped in that exact order. Each day the barge loads the next contiguous run of still-waiting units (zero or more, but always taken from the front of the queue) whose total weight does not exceed the barge's per-day capacity, then sails.
You may choose any integer per-day capacity, but it stays the same every day. Find the smallest capacity that lets the dock finish shipping every unit within at most D days.
Line 1: two integers n and D.
Line 2: n space-separated integers, the cargo weights in queue order.
A single integer: the smallest per-day capacity that finishes within D days.
Example 1
Input
5 2 3 2 5 1 4
Expected
10
Explanation
With 2 days the best plan ships {3,2,5} on day 1 (load 10) and {1,4} on day 2 (load 5), so the largest daily load is 10; no capacity below 10 can finish the queue in 2 days.
Example 2
Input
4 4 4 3 2 1
Expected
4
Explanation
With 4 days for 4 units, each unit can sail on its own day, so the capacity only needs to hold the heaviest unit, which is 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →