No.3471 ジャッジサーバーの負荷分散
yuki2006問題文
あるオンラインジャッジには $M$ 台のジャッジサーバー（サーバー $1, 2, \ldots, M$）があります。$N$ 個の提出がキューに順番に並んでおり、先頭から順に 1 つずつサーバーに割り当てていきます。
ここで、サーバーの負荷とは、そのサーバーに既に割り当てられた提出の実行時間の合計です。
各提出はその時点で現在の負荷が最も小さいサーバーに割り当てられます。負荷が最小のサーバーが複数ある場合は、番号が最も小さいサーバーに割り当てます。
提出 $i$ の実行時間は $T_i$ ミリ秒です。
すべての提出を割り当てた後、最後にジャッジが完了する時刻（すべてのサーバーの負荷の最大値）を求めてください。
入力
$N\ M$ $T_1\ T_2\ \ldots\ T_N$制約はすべて整数
- $1 \le M \le N \le 200{,}000$
- $1 \le T_i \le 10^9$
出力
すべてのジャッジが完了する時刻を 1 行で出力してください。 最後に改行してください。
サンプル
サンプル1
入力
5 2 2 3 7 5 1
出力
9
割り当ての過程:
提出1 (2ms) → サーバー1 (負荷: 2, 0)
提出2 (3ms) → サーバー2 (負荷: 2, 3)
提出3 (7ms) → サーバー1 (負荷: 9, 3)
提出4 (5ms) → サーバー2 (負荷: 9, 8)
提出5 (1ms) → サーバー2 (負荷: 9, 9)
完了時刻は $\max(9, 9) = 9$ です。
サンプル2
入力
3 3 10 20 30
出力
30
サーバーが 3 台あるので、各サーバーに 1 つずつ割り当てられます。最も実行時間の長い 30ms が完了時刻になります。
サンプル3
入力
4 1 2 3 7 5
出力
17
サーバーが 1 台しかないので、すべての提出を順番に実行します。合計 $2 + 3 + 7 + 5 = 17$ ms かかります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。