LG#P1182. 数列分段 Section II

数列分段 Section II

P1182 数列分段 Section II

题目描述

\hspace{15pt}对于给定的一个长度为 nn 的正整数数列 a1∼na_{1 \sim n},现要将其分成 mm(m≦nm \leqq n)段,并要求每段连续,且每段和的最大值最小。

\hspace{15pt}关于最大值最小,例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段。

\hspace{15pt}将其如下分段:

[4 2][4 5][1][4\ 2][4\ 5][1]

\hspace{15pt}第一段和为 66,第二段和为 99,第三段和为 11,和的最大值为 99。

\hspace{15pt}将其如下分段:

[4][2 4][5 1][4][2\ 4][5\ 1]

\hspace{15pt}第一段和为 44,第二段和为 66,第三段和为 66,和的最大值为 66。

\hspace{15pt}并且无论如何分段,最大值不会小于 66。

\hspace{15pt}所以,将数列 4 2 4 5 14\ 2\ 4\ 5\ 1 分成 33 段,每段和的最大值最小为 66。

输入格式

\hspace{15pt}第一行输入两个正整数 $n, m \left(1 \leqq n \leqq 10^5;\ 1 \leqq m \leqq n\right)$ 代表数列的长度和需要分成的段数。

\hspace{15pt}第二行输入 nn 个用空格隔开的正整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i < 10^8\right)$ 代表该数列。

输出格式

\hspace{15pt}在一行上输出一个正整数,代表每段和的最大值的最小值。

测试样例

5 3
4 2 4 5 1
6

数据范围与提示

\hspace{15pt}对于 20%20\% 的数据,n≦10n \leqq 10;

\hspace{15pt}对于 40%40\% 的数据,n≦1000n \leqq 1000;

\hspace{15pt}对于 100%100\% 的数据,1≦n≦1051 \leqq n \leqq 10^5,m≦nm \leqq n,ai<108a_i < 10^8,答案不超过 10910^9。