No.2922 Rose Garden
タグ : / 解いたユーザー数 171
作問者 :
kusirakusira
👑
tnodino
mymelochan
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もしくは右上の雲マークをクリックしてアカウントを作成してください。