問題一覧 > 通常問題

No.2217 Suffix+

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

問題文

長さ $N$ の数列 $A = (A_1,\dots,A_N)$ があります。

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

  • $1 \le i\le N$ を選び、$A_i,A_{i+1}, \dots,A_N$ にそれぞれ $i$ を加える。

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

入力

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

  • 入力は全て整数
  • $1 \le N \le 10^5$
  • $0 \le K \le 10^9$
  • $0 \le A_i \le 10^{14}$

出力

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

サンプル

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

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

  • $i = 1$ を選び、$A_1,A_2,A_3,A_4,A_5$ に $1$ を加える。$A=(4,5,3,2,1)$ となる。
  • $i = 3$ を選び、$A_3,A_4,A_5$ に $3$ を加える。$A=(4,5,6,5,4)$ となる。

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

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。