Minimize Maximum Segment Sum
Given an array of N positive integers, partition it into K contiguous subarrays (segments). Each element must belong to exactly one segment. The sum of a segment is the sum of its elements. You want to minimize the maximum sum among all K segments. Find this minimum possible value for the maximum segment sum.
Input
The first line contains two integers N and K (2 <= K <= N <= 200000). The second line contains N space-separated positive integers a_1, a_2, ..., a_N (1 <= a_i <= 10^9).
Output
Print a single integer: the minimum possible value of the maximum segment sum.
Constraints
2 <= K <= N <= 200000 1 <= a_i <= 10^9 Total sum of elements <= 2 * 10^14
Example 1
5 3 1 2 3 4 5
6
The array can be partitioned into [1, 2, 3], [4], [5]. Segment sums are 6, 4, 5. Max sum is 6. This is the minimum possible maximum sum.
Example 2
10 2 7 2 5 10 8 11 3 6 9 1
32
The minimum maximum sum is 30. For example, partition into [7, 2, 5, 10, 8] (sum 32) and [11, 3, 6, 9, 1] (sum 30) gives max 32. But partition [7, 2, 5, 10] (sum 24) and [8, 11, 3, 6, 9, 1] (sum 38) gives max 38. Partition [7, 2, 5, 10, 8, 11] (sum 43) and [3, 6, 9, 1] (sum 19) gives max 43. A parti
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 3 1 2 3 4 5
10 2 7 2 5 10 8 11 3 6 9 1