Split into k sub-arrays#9020
An array of elements and a number are given. Split the array into subarrays, using all elements of the original array (the order of elements must be preserved, and each element must belong to exactly one subarray).
For each such partition, compute the maximum of the sums of the subarrays. Your task is to perform the partitioning in such a way that this maximum is as small as possible. Find the minimum possible value of this maximum.
The first line contains two integers and k~(1 \le k \le n \le 10^6).
The second line contains positive integers — the elements of the array. Each number does not exceed 10^9.
Print the smallest possible value of the maximum sum among all valid partitions of the array into subarrays.
In the first example, an optimal partition is: \{1, 2\}, \{3\}, \{4\}. The subarray sums are: , , . The maximum among them is , which is the smallest possible value for k = 3.
In the second example, an optimal partition is: \{1, 2, 3, 4\}, \{2, 3, 4\}, \{2, 3, 1\}. The subarray sums are: , , . The maximum is , which is the smallest possible value for k = 3.
Example 1
Example 2