Capacity To Ship Packages Within D Days

Problem Packages with weights A[i] must ship IN ORDER within B days; each day the ship loads a consecutive prefix of the remaining packages up to its capacity. Find the minimum capacity that ships everything within B days.

Input / Output

• Input: int array A, int B. Output: minimum capacity.

Constraints

• n up to 5*10^4, weights up to 500; O(n log Σ) expected.

Example

• A = [1,2,3,4,5,6,7,8,9,10], B = 5 → 15 (days: [1..5], [6,7], [8], [9], [10]).