Packages with the given weights must be shipped in order, a group of consecutive packages each day, with the day's total weight at most the ship's capacity. Find the smallest capacity that ships everything within d days.
Input
The first line has n and d (1 ≤ d ≤ n ≤ 10⁵). The second line has the n weights (1 to 500).
Output
The smallest capacity.
Examples
Example 1 · Input
10 5 1 2 3 4 5 6 7 8 9 10
Expected output
15
Example 2 · Input
6 3 3 2 2 4 1 4
Expected output
6
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For a capacity c, a greedy pass tells you how many days are needed.
Hint 2
The answer lies between max(weights) and sum(weights).
Hint 3
Binary search for the smallest capacity whose day count is at most D.
Solution
Show one correct solution (try it yourself first)
n, d = map(int, input().split())
weights = list(map(int, input().split()))
def days(capacity):
count, load = 1, 0
for w in weights:
if load + w > capacity:
count += 1
load = 0
load += w
return count
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if days(mid) <= d:
hi = mid
else:
lo = mid + 1
print(lo)