/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は 1 本の長いロープを持っています。
このロープは N 個の区間に分かれており、各区間には左から順に 1 から N までの番号が付けられています。区間 i（1 \leq i \leq N）の長さは A_i であり、ロープ全体の長さは A_1 + A_2 + \cdots + A_N です。
高橋君はこのロープをちょうど K 本に分割したいと考えています。ロープを切ることができるのは、区間 i と区間 i+1 の間の境目（1 \leq i \leq N-1）に限られます。ちょうど K 本に分割するには、N - 1 箇所ある境目のうちちょうど 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 3 1 2 3 4 5
出力例 1
6
入力例 2
8 4 3 1 4 1 5 9 2 6
出力例 2
9
入力例 3
10 3 100 200 300 400 500 600 700 800 900 1000
出力例 3
2100
Score : 400 pts
Problem Statement
Takahashi has one long rope.
This rope is divided into N sections, and each section is numbered from 1 to N from left to right. The length of section i (1 \leq i \leq N) is A_i, and the total length of the rope is A_1 + A_2 + \cdots + A_N.
Takahashi wants to divide this rope into exactly K pieces. The rope can only be cut at the boundary between section i and section i+1 (1 \leq i \leq N-1). To divide the rope into exactly K pieces, he selects exactly K - 1 of the N - 1 available boundaries and cuts at those positions. Sections cannot be removed, and every section must belong to exactly one of the resulting pieces.
As a result, each piece after the division consists of one or more consecutively numbered sections. The length of each piece is the sum of the lengths of the sections it contains.
Takahashi wants to minimize the length of the longest piece among the K pieces after the division.
Find the minimum possible length of the longest piece among the K pieces when the cuts are made optimally.
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 sections and an integer K representing the number of pieces after division, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the lengths of the N sections, separated by spaces.
Output
Print in one line the minimum possible length of the longest piece among the K pieces when the cuts are made optimally.
Sample Input 1
5 3 1 2 3 4 5
Sample Output 1
6
Sample Input 2
8 4 3 1 4 1 5 9 2 6
Sample Output 2
9
Sample Input 3
10 3 100 200 300 400 500 600 700 800 900 1000
Sample Output 3
2100