問題一覧 > 通常問題

No.1736 Princess vs. Dragoness

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

注意

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

問題文

あなたは $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$ に初期化される。


魔法を適切に使うことで、すべてのモンスターの体力を $0$ 以下にすることができるならYes、できないならNoと出力してください。

制約

  • 入力は全て整数
  • $ 1 \leq N \leq 3000 $
  • $ 0 \leq A, B \leq 3000 $
  • $ 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$

出力

YesNoで出力せよ。 最後に改行すること。

サンプル

サンプル1
入力
4 1 1 8 9
6 4 2 2
出力
Yes

まず、魔法Aをモンスター $1$ を対象に使います。そうすると、モンスターの体力は-2 4 2 2になります。

その後、魔法Bを $1$ 回使うことで、以下の効果が順に起こります。

  • 初め、$P = 9$ である。
  • $i = 1$ : 魔法Bを使う前のモンスター $1$ の体力は-2であるため、何も起こらない。
  • $i = 2$ : 魔法Bを使う前のモンスター $2$の体力は4である。 $D = min(P, H_2) = 4$ となり、モンスター $2$ の体力を0にして、$P = 9 - 4 = 5$ となる。
  • $i = 3$ : 魔法Bを使う前のモンスター $3$の体力は2である。 $D = min(P, H_3) = 2$ となり、モンスター $3$ の体力を0にして、$P = 5 - 2 = 3$ となる。
  • $i = 4$ : 魔法Bを使う前のモンスター $4$の体力は2である。 $D = min(P, H_4) = 2$ となり、モンスター $4$ の体力を0にして、$P = 3 - 2 = 1$ となる。

よって、モンスターの体力は-2 0 0 0となり、すべて $0$ 以下にできているので、Yesを出力してください。

サンプル2
入力
1 2 0 8 9
9
出力
Yes

使うことのできない魔法があるかもしれません。

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

どのように魔法を使っても、モンスターすべての体力を $0$ 以下にすることができません。

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