A chocolate bar is a row of n chunks, chunk i having sweetness s[i]. You will break the bar into exactly p contiguous, non-empty pieces (each piece is a run of neighboring chunks, and together the pieces cover the whole bar with no gaps or overlaps). The sweetness of a piece is the sum of its chunks.
After splitting, the weakest piece is the one with the smallest total sweetness. Choose the split that makes the weakest piece as sweet as possible, and report that weakest piece's sweetness.
Line 1: two integers n and p.
Line 2: n space-separated integers, the chunk sweetness values.
A single integer: the maximum possible sweetness of the weakest piece.
Example 1
Input
6 3 1 2 3 4 5 6
Expected
6
Explanation
Splitting into {1,2,3}, {4,5}, {6} gives piece sums 6, 9, 6, so the weakest is 6; no split into 3 pieces makes the weakest piece exceed 6.
Example 2
Input
4 4 5 1 4 2
Expected
1
Explanation
Four pieces from four chunks forces each chunk to stand alone, so the weakest piece is the smallest chunk, which is 1.
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 →