Array Division
Split the array into `k` consecutive pieces minimising the largest piece sum. Pieces may be empty; since `k ≤ n` this does not change the optimum.
You are given an array containing positive integers.
Your task is to divide the array into subarrays so that the maximum sum in a subarray is as small as possible.
Input
The first input line contains two integers and : the size of the array and the number of subarrays in the division.
The next line contains integers : the contents of the array.
Output
Print one integer: the maximum sum in a subarray in the optimal division.
Constraints
Example
Input:
5 3 2 4 7 3 5
Output:
8
Explanation: An optimal division is where the sums of the subarrays are . The largest sum is the last sum .
Statement © the CSES Problem Set. View the original
The specification is at TalosEval/Problems/CSES/ArrayDivision/Spec.lean.
Submit
binary + proofResults
No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.
Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.