問題一覧 > 通常問題

No.1211 円環はお断り

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 42
作問者 : ThistleThistle / テスター : RhoRho
3 ProblemId : 4861 / 出題時の順位表
問題文最終更新日: 2020-08-30 12:42:56

問題文

ある日、Rhoたち $K$ 人の魔法少女は、アルティメットThistleから $N$ 個のビーズが連なった円環を受け取りました。
$N$ 個のビーズそれぞれには、$1,2,\dots,N$ と番号が振られています。
$i(2 \leq i \leq N-1)$ 番目のビーズはビーズ $i-1$ と $i+1$ に隣り合っていて、$1$ 番目のビーズはビーズ $N$ と $2$、$N$ 番目のビーズはビーズ $N-1$ と $1$ に隣り合っています。

これらのビーズにはアルティメットThistleが魔力を込めていて、魔力の質によって1つ1つに価値が存在します。
具体的には、$i$ 番目のビーズの価値は $A_i$ です。

彼女たちはこの円環を連続するビーズから成る $K$ 個の区間に分割し、これを $K$ 人で分けあうことにしました。
ただ、分け方が平等でないと抗争に発展してしまうので、それぞれの分け前のビーズの価値の総和の最小値を $M$ としたとき、$M$ が最大になるように分割することにしました。

さて、彼女たちのマスコットであるあなたは、彼女たちを陰から導くため、上のような分割をしたときの $M$ を求めることにしました。

入力

$N\ K$
$A_1\ A_2\ \dots\ A_N$

入力は全て整数である
$1\leq K\leq N\leq 10^5$
$1\leq A_i\leq 10^9 (1\leq i\leq N)$

出力

$M$ の最大値を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
6 4
8 6 9 1 2 1
出力
4

(8),(6),(9),(1,2,1)のように分割したときが最適となり、この時のMは4です。

サンプル2
入力
15 7
12 9 11 15 15 11 9 7 2 3 1 14 15 6 11
出力
15

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。