問題一覧 > 通常問題

No.1808 Fullgold Alchemist

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : MasKoaTSMasKoaTS / テスター : Kanten4205Kanten4205 👑 ygussanyygussany
5 ProblemId : 7006 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-06 17:58:19

問題文

$1,2, \dots ,N$ の番号が付いた $N$ 種類の鉱石がそれぞれ $A_{1},A_{2}, \dots ,A_{N}$ 個あります。

錬金術師のコアさんは、これらに対して「次の $2$ 種類の操作のうちどちらか一方を自由に選び、これを実行する」
という行為を $0$ 回以上好きな回数だけ繰り返します。

  • $1 \leq i < j \leq N$ を満たす整数の組 $(i,j)$ を $1$ つ選び、 鉱石 $i$ を $1$ 個消費して鉱石 $j$ を $1$ 個生成する。

  • 鉱石 $1,2, \dots ,N$ を $M$ 個ずつ消費して金塊を $1$ 個生成する。

このとき、コアさんは金塊を最大でいくつ生成できますか?

制約

  • $1 \leq N \leq 2 \times 10^{5}$

  • $1 \leq M \leq 10^{9}$

  • $0 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
  • $1$ 行目には $N$ と $M$ がこの順に空白区切りで与えられる

  • $2$ 行目には $A_{1},A_{2},\dots,A_{N}$ がこの順に空白区切りで与えられる

出力

答えを $1$ 行に出力し、最後に改行してください。

サンプル

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

鉱石 $1$ を $1$ 個消費して鉱石 $3$ を $1$ 個生成する操作を $2$ 回繰り返した後、
鉱石 $1, 2, 3, 4$ を $3$ 個ずつ消費すれば、金塊を $1$ 個生成できます。

金塊を $2$ 個以上生成することはできません。

サンプル2
入力
10 2
9 8 7 6 5 4 3 2 1 0
出力
2
サンプル3
入力
7 10
0 100 100 100 100 100 100
出力
0

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