問題一覧 > 通常問題

No.1739 Princess vs. Dragoness (& AoE)

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 122
作問者 : ShirotsumeShirotsume / テスター : とりゐとりゐ nok0nok0
1 ProblemId : 7218 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-12 20:52:29

注意

この問題はB問題と問題設定が共通しています。あらかじめ両方の問題文を読むことをお勧めします。

問題文

あなたは $N$ 体のモンスターと戦っています。モンスターには $1, 2, 3, \dots N$ の番号がついていて、$i$ 番目のモンスターの体力は $H_i$ です。

あなたは以下に示す魔法Aを $A$ 回、魔法Bを $B$ 回まで使うことができます。


    魔法A: モンスターを $1$ 体選び、そのモンスターの体力を $X$ 減らす。


    魔法B: 番号の小さい順にモンスターの体力が $0$ になるよう体力を減らしていき、合計で $Y$ だけ体力を減らす。より正確には、以下の効果が発生する。

      魔法Bによって減らすことのできる体力の合計を $P$ とする。魔法Bを使った直後、$P = Y$ である。

      魔法Bを使う直前のモンスターの体力を $H_1', H_2', \dots H_N'$ とする。$i = 1, 2, \dots N$ の順に、次のことを行う。

      • $H_i' ≤ 0$ なら、何もしない。
      • $H_i' > 0$ なら、モンスター $i$ の体力を $D = \mathrm{min}(P, H_i')$ だけ減らす。その後、$P$ の値を $D$ 減らす。

      魔法Bを複数回使う場合、毎回 $P = Y$ に初期化される。


$1$ 人だけの力ではモンスターすべての体力を $0$ 以下にできないと思ったあなたは、非負整数 $K$ を $1$ つ定めて、友人の魔術師に頼んであらかじめすべてのモンスターの体力を $K$ ずつ減らしてもらうことにしました。

体力を減らしてもらった後に、$2$ 種類の魔法を使うことによってモンスターすべての体力を $0$ 以下にすることができる $K$ の最小値を求めてください。

制約

  • 入力は全て整数
  • $ 1 \leq N \leq 10^5 $
  • $ 0 \leq A, B \leq 10^5 $
  • $ 1 \leq X, Y \leq 10^9 $
  • $ 1 \leq H_i \leq 10^9 $

入力

入力は以下の形式で標準入力から与えられる。
$N$ $A$ $B$ $X$ $Y$
$H_1$ $H_2$ $\dots$ $H_N$

出力

魔法Aと魔法Bを用いてすべてのモンスターの体力を $0$ 以下にできる最小の非負整数 $K$ を出力せよ。 最後に改行すること。

サンプル

サンプル1
入力
3 1 1 8 9
14 13 5
出力
5

初めに友人の魔術師にモンスターすべての体力を $5$ 減らしてもらうと、モンスターの体力は 9 8 0になります。

その後、魔法Aと魔法Bをそれぞれ $1$ 回ずつ使うことですべてのモンスターの体力を $0$ 以下にすることができます。

サンプル2
入力
5 2 1 85 81
50 98 96 21 69
出力
20

サンプル3
入力
15 1 6 4571 4268
6955 1118 6093 7840 4109 2330 5533 2202 2844 1595 590 5776 8883 7632 3759
出力
2934

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