No.1736 Princess vs. Dragoness
タグ : / 解いたユーザー数 176
作問者 :
Shirotsume
/ テスター :
nok0
とりゐ
問題文
あなたは $N$ 体のモンスターと戦っています。モンスターには $1, 2, 3, \dots N$ の番号がついていて、$i$ 番目のモンスターの体力は $H_i$ です。
あなたは以下に示す魔法Aを $A$ 回、魔法Bを $B$ 回まで使うことができます。
- $H_i' ≤ 0$ なら、何もしない。
- $H_i' > 0$ なら、モンスター $i$ の体力を $D = \mathrm{min}(P, H_i')$ だけ減らす。その後、$P$ の値を $D$ 減らす。
魔法A: モンスターを $1$ 体選び、そのモンスターの体力を $X$ 減らす。
魔法B: 番号の小さい順にモンスターの体力が $0$ になるよう体力を減らしていき、合計で $Y$ だけ体力を減らす。より正確には、以下の効果が発生する。
魔法Bによって減らすことのできる体力の合計を $P$ とする。魔法Bを使った直後、$P = Y$ である。
魔法Bを使う直前のモンスターの体力を $H_1', H_2', \dots H_N'$ とする。$i = 1, 2, \dots N$ の順に、次のことを行う。
魔法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$
出力
YesかNoで出力せよ。
最後に改行すること。
サンプル
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。