/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は、N 個の部品が一列に連結された丸太を持っています。部品には左から順に 1, 2, \ldots, N の番号が付けられており、部品 i の長さは A_i です。
隣接する部品の間には境目があり、その箇所は N - 1 箇所あります。すなわち、部品 i と部品 i + 1 の間の境目 (1 \leq i \leq N - 1) です。高橋君はこれらの境目の中から K 箇所を選んで切断し、丸太を K + 1 個の断片に分割します。
各断片の長さは、その断片に含まれる部品の長さの合計で定まります。K + 1 個の断片の長さの最大値を M とします。
切断箇所の選び方を最適にしたとき、M の値として達成できる最小値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N - 1
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、部品の数を表す整数 N と、切断箇所の数を表す整数 K が、空白区切りで与えられる。
- 2 行目には、各部品の長さを表す整数 A_1, A_2, \ldots, A_N が、空白区切りで与えられる。
出力
切断箇所を最適に選んだときの、K + 1 個の断片の長さの最大値 M の最小値を 1 行で出力せよ。
入力例 1
5 2 3 5 4 7 6
出力例 1
11
入力例 2
4 1 1 2 3 4
出力例 2
6
入力例 3
10 3 5 8 3 12 7 2 9 6 4 10
出力例 3
19
入力例 4
20 5 14 7 23 11 5 19 8 30 12 6 17 25 3 9 21 16 28 4 13 10
出力例 4
55
入力例 5
2 1 1000000000 1000000000
出力例 5
1000000000
Score : 366 pts
Problem Statement
Takahashi has a log consisting of N parts connected in a row. The parts are numbered 1, 2, \ldots, N from left to right, and the length of part i is A_i.
There are boundaries between adjacent parts, and there are N - 1 such boundaries. Namely, the boundary between part i and part i + 1 (1 \leq i \leq N - 1). Takahashi chooses K of these boundaries to cut, dividing the log into K + 1 fragments.
The length of each fragment is determined by the sum of the lengths of the parts contained in that fragment. Let M be the maximum length among the K + 1 fragments.
Find the minimum possible value of M when the cut positions are chosen optimally.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N - 1
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of parts and an integer K representing the number of cuts, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the lengths of the parts, separated by spaces.
Output
Print in one line the minimum value of M, the maximum length among the K + 1 fragments, when the cut positions are chosen optimally.
Sample Input 1
5 2 3 5 4 7 6
Sample Output 1
11
Sample Input 2
4 1 1 2 3 4
Sample Output 2
6
Sample Input 3
10 3 5 8 3 12 7 2 9 6 4 10
Sample Output 3
19
Sample Input 4
20 5 14 7 23 11 5 19 8 30 12 6 17 25 3 9 21 16 28 4 13 10
Sample Output 4
55
Sample Input 5
2 1 1000000000 1000000000
Sample Output 5
1000000000