题目描述
对于给定的一个长度为
N
N 的正整数数列
A
A ，现要将其分成
M
M 段，并要求每段连续，且每段和的最大值最小。
例如，将数列
4 \ \ 2 \ \ 4 \ \ 5 \ \ 1
4 2 4 5 1 要分成
3
3 段：
若分为
[4
[4
2][4
2][4
5][1]
5][1]，各段的和分别为
6, 9, 1
6,9,1 ，和的最大值为
9
9；
若分为
[4][2
[4][2
4][5
4][5
1]
1]，各段的和分别为
4, 6, 6
4,6,6 ，和的最大值为
6
6；
并且无论如何分段，最大值不会小于
6
6。
所以可以得到要将数列
4 \ \ 2 \ \ 4 \ \ 5 \ \ 1
4 2 4 5 1 要分成
3
3 段，每段和的最大值最小为
6
6 。
输入
第
1
1 行包含两个正整数
N
N，
M
M；
第
2
2 行包含
N
N 个空格隔开的非负整数
A_i
Ai
，含义如题目所述。
输出
仅包含一个正整数，即每段和最大值最小为多少。
样例输入
5 3
4 2 4 5 1
样例输出
6
提示
数据范围与提示
对于
20\%
20%的数据，有
N \leq 10
N≤10；
对于
40\%
40% 的数据，有
N \leq 1000
N≤1000；
对于
100\%
100%的数据，有
N \leq 10^5
N≤105，
M \leq N
M≤N，
A_i
Ai
之和不超过
10^9
109 。
来源/分类
ybttg 二分