- Time limit: 1.00 s
- Memory limit: 512 MB
You are given an array containing n positive integers.
Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.
The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.
The next line contains n integers x_1,x_2,\ldots,x_n: the contents of the array.
Print one integer: the maximum sum in a subarray in the optimal division.
- 1 \le n \le 2 \cdot 10^5
- 1 \le k \le n
- 1 \le x_i \le 10^9
5 3 2 4 7 3 5
Explanation: An optimal division is [2,4],,[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.