問題一覧 > 通常問題

No.1736 Princess vs. Dragoness

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 181
作問者 : Shirotsume / テスター : nok0 とりゐ
お気に入りにしたユーザー ProblemId : 7163 / 自分の提出
問題文最終更新日: 2022-07-20 02:04:07
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 322 (順位表) の他の問題:

Problem Statement

You are fighting $N$ monsters. The monsters are numbered $1, 2, 3, \dots N$, and the health of the $i$-th monster is $H_i$.

You can use Spell A, described below, up to $A$ times and Spell B up to $B$ times.


    Spell A: Choose $1$ monster and decrease its health by $X$.


    Spell B: Decreases the health of the monsters in ascending order of their numbers so that their health becomes $0$, decreasing health by $Y$ in total. More precisely, the following effect occurs.

      Let $P$ be the total amount of health that Spell B can decrease. Immediately after Spell B is used, $P = Y$.

      Let $H_1', H_2', \dots H_N'$ be the health of the monsters immediately before Spell B is used. For $i = 1, 2, \dots N$, in this order, do the following.

      • If $H_i' ≤ 0$, do nothing.
      • If $H_i' > 0$, decrease the health of monster $i$ by $D = \mathrm{min}(P, H_i')$. Then, decrease the value of $P$ by $D$.

      If Spell B is used multiple times, $P = Y$ is initialized each time.


If you can make the health of all monsters $0$ or less by using the spells appropriately, print Yes; otherwise, print No.

Constraints

  • All input values are integers.
  • $ 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 $

Input

The input is given from standard input in the following format. 
$N$ $A$ $B$ $X$ $Y$
$H_1$ $H_2$ $\dots$ $H_N$

Output

Print Yes or No. Print a newline at the end.

Sample

Sample 1
Input
4 1 1 8 9
6 4 2 2
Output
Yes

First, use Spell A on monster $1$. The health of the monsters then becomes -2 4 2 2.

After that, by using Spell B $1$ time, the following effects occur in order.

  • Initially, $P = 9$.
  • $i = 1$ : The health of monster $1$ before Spell B is used is -2, so nothing happens.
  • $i = 2$ : The health of monster $2$ before Spell B is used is 4. We have $D = min(P, H_2) = 4$, so the health of monster $2$ becomes 0, and $P = 9 - 4 = 5$.
  • $i = 3$ : The health of monster $3$ before Spell B is used is 2. We have $D = min(P, H_3) = 2$, so the health of monster $3$ becomes 0, and $P = 5 - 2 = 3$.
  • $i = 4$ : The health of monster $4$ before Spell B is used is 2. We have $D = min(P, H_4) = 2$, so the health of monster $4$ becomes 0, and $P = 3 - 2 = 1$.

Thus, the health of the monsters becomes -2 0 0 0, and all of them are $0$ or less, so print Yes.

Sample 2
Input
1 2 0 8 9
9
Output
Yes

There may be a spell that cannot be used.

Sample 3
Input
3 1 1 8 9
14 13 5
Output
No

No matter how the spells are used, the health of all monsters cannot be made $0$ or less.

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