/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は運送会社で配達計画を担当しています。
今日は N 個の荷物を K 台のトラックで配達する計画を立てる必要があります。
各荷物には 1 から N までの番号が付けられており、荷物 i の重さは A_i です。
配達の効率化のため、荷物 1, 2, \ldots, N をこの順に並べた列を、それぞれ 1 個以上の荷物からなる K 個の連続区間に分割し、各区間の荷物をそれぞれ 1 台のトラックに割り当てることにしました。すべての荷物はちょうど 1 つの区間に属し、K 個の区間と K 台のトラックは 1 対 1 に対応します。
各トラックについて、そのトラックに割り当てられた荷物の重さの合計を、そのトラックの 負担量 と呼ぶことにします。
高橋君は、K 台のトラックの負担量のうち最も小さい値をできるだけ大きくしたいと考えています。
すべての分割方法を考えたとき、「K 台のトラックの負担量の最小値」として達成可能な最大値を求めてください。
制約
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、荷物の個数を表す整数 N と、トラックの台数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各荷物の重さを表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
最適な分割を行ったときの、K 台のトラックの負担量の最小値として達成可能な最大値を 1 行で出力してください。
入力例 1
5 2 1 2 3 4 5
出力例 1
6
入力例 2
7 3 3 1 4 1 5 9 2
出力例 2
6
入力例 3
10 4 100 200 150 300 50 250 400 100 350 200
出力例 3
450
Score : 400 pts
Problem Statement
Takahashi is in charge of delivery planning at a shipping company.
Today, he needs to create a plan to deliver N packages using K trucks.
Each package is numbered from 1 to N, and the weight of package i is A_i.
To improve delivery efficiency, he decided to arrange the packages 1, 2, \ldots, N in this order and divide them into K contiguous segments, each containing at least 1 package, and assign the packages in each segment to one truck. Every package belongs to exactly one segment, and there is a one-to-one correspondence between the K segments and the K trucks.
For each truck, the sum of the weights of the packages assigned to that truck is called the load of that truck.
Takahashi wants to maximize the smallest load among the K trucks.
Considering all possible ways to divide the packages, find the maximum possible value of "the minimum load among the K trucks."
Constraints
- 1 \leq K \leq N \leq 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of packages and an integer K representing the number of trucks, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the weight of each package, separated by spaces.
Output
Print in one line the maximum possible value of the minimum load among the K trucks when the packages are divided optimally.
Sample Input 1
5 2 1 2 3 4 5
Sample Output 1
6
Sample Input 2
7 3 3 1 4 1 5 9 2
Sample Output 2
6
Sample Input 3
10 4 100 200 150 300 50 250 400 100 350 200
Sample Output 3
450