問題一覧 > 通常問題

No.2922 Rose Garden

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 171
作問者 : hirayuu_yc / テスター : kusirakusira 👑 loop0919 nouka28 tnodino mymelochan uruzunyaa
お気に入りにしたユーザー ProblemId : 11105 / 自分の提出
問題文最終更新日: 2025-02-07 23:09:55
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
第3回緑以下コンテスト (順位表) の他の問題:

Problem Statement

$N$ platforms are arranged in $1$ horizontal row. The platforms are numbered $1,2,\dots,N$ from left to right, and the height of platform $i$ is $H_i$.

Midori is currently on platform $1$ with stamina $S$ and altitude $H_1$. She wants to land on platform $N$ by repeating the following operation any number of times.

  • Do one of the following.
    • Decrease her stamina by $1$ and increase her altitude by $B$. This operation cannot be performed when her stamina is $0$.
    • When she is on platform $i$, move to platform $i+1$ while keeping her altitude. This operation cannot be performed when her altitude is less than $H_{i+1}$ or when she is on platform $N$.
    • When she is on platform $i$, land on platform $i$. Her altitude then becomes $H_i$, and her stamina becomes exactly $S$.

Determine whether it is possible for her to eventually land on platform $N$.

Constraints

  • $1\leq N\leq 2\times 10^5$
  • $1\leq S\leq 10^3$
  • $1\leq B\leq 10^9$
  • $0\leq H_i\leq 10^9 (1\leq i\leq N)$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N\ S\ B$
$H_1\ H_2\ \dots\ H_N$

Output

Print Yes if it is possible to eventually land on platform $N$, and No otherwise.

Sample

Sample 1
Input
3 3 12
0 10 30
Output
Yes

Here is one way to land on platform $3$.

  • Initially, she is on platform $1$ with stamina $3$ and altitude $0$.
  • Increase her altitude by $12$. Her altitude becomes $12$ and her stamina becomes $2$.
  • Move to platform $2$.
  • Land on platform $2$. Her altitude becomes $10$ and her stamina becomes $3$.
  • Increase her altitude by $12$. Her altitude becomes $22$ and her stamina becomes $2$.
  • Increase her altitude by $12$. Her altitude becomes $34$ and her stamina becomes $1$.
  • Move to platform $3$.
  • Land on platform $3$. Her altitude becomes $30$ and her stamina becomes $3$.
Sample 2
Input
4 1 100
0 100 200 0
Output
Yes

Note that her stamina is allowed to reach $0$, and that she can move to the next platform if her altitude is equal to its height.

Sample 3
Input
10 5 1
1 0 0 0 0 0 0 0 0 7
Output
No

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