Smallest truck that clears the backlog in D days
A courier company in Karachi has a queue of parcels with known weights that must be delivered in the given order. Every day one truck is loaded with the next parcels in the queue, as many as fit, without exceeding the truck's weight capacity (a parcel can never be split). The company must clear the whole queue within D days and wants to rent the truck with the smallest capacity that still makes it.
Task: the first line holds n and D (1 ≤ D ≤ n ≤ 200). The second line holds the n parcel weights (integers from 1 to 500) in queue order. Each day the truck takes the longest prefix of the remaining queue that fits. Print the minimum integer capacity that finishes all parcels in at most D days.
Sample test
Input
10 5 1 2 3 4 5 6 7 8 9 10
Expected output
15
Your answer is also checked against 5 hidden tests.
Need a hint?
If a capacity works, any bigger capacity also works. That lets you search for the answer instead of trying every value.
Log in or create a free account to run your code, submit and earn points.
Run your code to see the output here. Ctrl + Enter also runs it.