Home => ProblemSet => 1.11-18:数组分段
Problem1732--1.11-18:数组分段

1732: 1.11-18:数组分段

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 0
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

已知一个长度为 n 的数组 a,把它切分成 m 个连续的段,使得每段之和的最大值最小。求这个最小值。

Input

第一行正整数n和m,空格分隔
第二行n个整数,空格分隔

Output

一个整数,表示最小值

Sample Input Copy

3 2
1 2 3

Sample Output Copy

3

HINT

样例说明:
1 2 3切为2段,可以是[1][2 3],最大和为5;也可以是[1 2][3],最大和为3


1 ≤ m ≤ n ≤ 105
0 ≤ ai ≤ 109

Source/Category