最大部分和が最小になるように配列を分割
整数
n 個 と整数 k が与えられたとき、配列を k 個の連続する部分に分割して、各部分の合計のうち最大のものができるだけ小さくなるようにしてください。入力
最初の行には、2 つの整数
n (1 ≤ n ≤ ) と k (1 ≤ k ≤ n) が与えられます。次の行には、空白区切りの整数 ( ≤ ≤ ) が与えられます。
出力
プログラムは、最大部分配列の合計ができるだけ小さくなるように求めた結果を出力してください。
例
入力 | 出力 |
5 2
1 2 3 6 2 | 8 |
5 3
1 2 10 3 2 | 10 |
解説
[1 2 3] [6 2]⇒ 最大部分配列の合計は 6 + 2 = 8
[1 2] [10] [3 2]⇒ 最大部分配列の合計は 10
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB