LG#P1182. 数列分段 Section II
数列分段 Section II
P1182 数列分段 Section II
题目描述
对于给定的一个长度为 的正整数数列 ,现要将其分成 ()段,并要求每段连续,且每段和的最大值最小。
关于最大值最小,例如一数列 要分成 段。
将其如下分段:
第一段和为 ,第二段和为 ,第三段和为 ,和的最大值为 。
将其如下分段:
第一段和为 ,第二段和为 ,第三段和为 ,和的最大值为 。
并且无论如何分段,最大值不会小于 。
所以,将数列 分成 段,每段和的最大值最小为 。
输入格式
第一行输入两个正整数 $n, m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq n\right)$ 代表数列的长度和需要分成的段数。
第二行输入 个用空格隔开的正整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i < 10^8\right)$ 代表该数列。
输出格式
在一行上输出一个正整数,代表每段和的最大值的最小值。
测试样例
5 3
4 2 4 5 1
6
数据范围与提示
对于 的数据,;
对于 的数据,;
对于 的数据,,,,答案不超过 。