/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2020/12/27 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
左右に横たわる細長い棒に N - 1 箇所の切れ込みがあります。この棒を全ての切れ込みで切断すると、左から順に長さ A_1, A_2, A_3, \dots, A_N の N 本の棒に分かれます。
あなたは、N - 1 箇所の切れ込みのうちいくつかを選び、選んだ箇所でこの棒を切断してから出荷します。(1 箇所も選ばなくても、全部選んでも構いません。)
あまり長い棒は扱いに困るので、切断後に全ての棒の長さが L 以下になるように切ります。また、棒の長さに偏りが生じないように、切断後の一番短い棒の長さをできる限り長くします。
切断後の一番短い棒の長さとして考えられる最大値を求めてください。
制約
- 1 \le N \le 2 \times 10^5
- 1 \le L \le 10^{15}
- 1 \le A_i \le \min(10^9, L)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L A_1 A_2 A_3 \dots A_N
出力
切断後の一番短い棒の長さとして考えられる最大値を出力せよ。
入力例 1
5 10 3 4 1 2 4
出力例 1
7
左から 2 番目の切れ込みだけで切断すると、出来上がる 2 つの棒の長さはそれぞれ 3 + 4 = 7, 1 + 2 + 4 = 7 となり、一番短い棒の長さは 7 となります。
これが最大です。
入力例 2
8 10 7 2 1 5 3 2 5 2
出力例 2
9
左から 2, 5 番目の切れ込みで切断すると、長さ 9 の棒が 3 本出来上がります。
入力例 3
13 10000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
6000000000
長さ 6000000000 の棒と、長さ 7000000000 の棒が一つずつできるような切り方が最適です。
Score : 6 points
Warning
Do not make any mention of this problem until December 27, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
We have a long and narrow stick with N - 1 notches, lying from left to right. Cutting this stick at all of the notches will separate this stick into N sticks of length A_1, A_2, A_3, \dots, A_N from left to right.
You will choose some of the notches (possibly none or all), cut the stick at the chosen notches, and ship the resulting sticks.
Too long sticks are troublesome, so you will make the cuts so that the length of every resulting stick is at most L. Also, to make the lengths of the resulting sticks as uniform as possible, you will maximize the length of the shortest resulting stick.
Find the maximum possible length of the shortest resulting stick.
Constraints
- 1 \le N \le 2 \times 10^5
- 1 \le L \le 10^{15}
- 1 \le A_i \le \min(10^9, L)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L A_1 A_2 A_3 \dots A_N
Output
Print the maximum possible length of the shortest resulting stick.
Sample Input 1
5 10 3 4 1 2 4
Sample Output 1
7
Cutting the stick at just the 2-nd notch from the left results in two sticks of length 3 + 4 = 7 and 1 + 2 + 4 = 7, the minimum of which is 7.
This is the maximum possible result.
Sample Input 2
8 10 7 2 1 5 3 2 5 2
Sample Output 2
9
Cutting the stick at the 2-nd and 5-th notches from the left results in three sticks of length 9 each.
Sample Input 3
13 10000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
6000000000
It is optimal to make two sticks of lengths 6000000000 and 7000000000.