問題一覧 > 通常問題

No.2217 Suffix+

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 161
作問者 : stoq / テスター : ぷら Shirotsume
6 ProblemId : 9118 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-18 08:26:34

問題文

長さ NN の数列 A=(A1,…,AN)A = (A_1,\dots,A_N) があります。

あなたは次の操作を 00 回以上 KK 回以下行うことができます。

  • 1≤i≤N1 \le i\le N を選び、Ai,Ai+1,…,ANA_i,A_{i+1}, \dots,A_N にそれぞれ ii を加える。

操作後の AA の最小値として考えられる最大値を求めてください。

入力

NN KK
A1A_1 …\dots ANA_N

  • 入力は全て整数
  • 1≤N≤1051 \le N \le 10^5
  • 0≤K≤1090 \le K \le 10^9
  • 0≤Ai≤10140 \le A_i \le 10^{14}

出力

操作後の AA の最小値として考えられる最大値を出力してください。

サンプル

サンプル1
入力
5 2
3 4 2 1 0
出力
4

例えば、次のような手順が最適です。

  • i=1i = 1 を選び、A1,A2,A3,A4,A5A_1,A_2,A_3,A_4,A_5 に 11 を加える。A=(4,5,3,2,1)A=(4,5,3,2,1) となる。
  • i=3i = 3 を選び、A3,A4,A5A_3,A_4,A_5 に 33 を加える。A=(4,5,6,5,4)A=(4,5,6,5,4) となる。

AA の最小値を 44 より大きくすることはできないため、最小値の最大値は 44 です。

サンプル2
入力
3 0
0 0 0
出力
0

サンプル3
入力
10 100
901 780 604 576 569 569 515 488 379 100
出力
724

サンプル4
入力
1 1000000000
100000000000000
出力
100001000000000

オーバーフローに注意してください。

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