No.2922 Rose Garden
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 169
作問者 :
hirayuu_yc
/ テスター :
kusirakusira
loop0919
nouka28
tnodino
mymelochan
Nyaa Uruzu
タグ : / 解いたユーザー数 169
作問者 :
hirayuu_yc
/ テスター :
kusirakusira
loop0919
nouka28
tnodino
mymelochan
Nyaa Uruzu
問題文最終更新日: 2024-10-12 14:44:26
問題文
$N$ 個の足場が横 $1$ 列に並んでいます。足場には左から $1,2,\dots,N$ と番号がつけられていて、足場 $i$ の高さは $H_i$ です。
今、みどりちゃんがスタミナ $S$ 、高度 $H_1$ の状態で足場 $1$ にいます。みどりちゃんは、以下の操作を好きな回数繰り返すことで足場 $N$ に着地したいです。
- 以下のどれかを行う。
- スタミナを $1$ 減らして高度を $B$ 上げる。ただし、スタミナが $0$ のときはこの操作を行うことができない。
- 足場 $i$ にいるとき、高度を保ったまま足場 $i+1$ に移動する。ただし、高度が $H_{i+1}$ 未満のとき、または足場 $N$ にいるときこの操作を行うことができない。
- 足場 $i$ にいるとき、足場 $i$ に着地する。このとき、高度が $H_i$ になり、スタミナがちょうど $S$ になる。
最終的に足場 $N$ に着地することが可能か判定してください。
制約
- $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)$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
$N\ S\ B$ $H_1\ H_2\ \dots\ H_N$
出力
最終的に足場 $N$ に着地することが可能であれば Yes を、そうでなければ No を出力せよ。
サンプル
サンプル1
入力
3 3 12 0 10 30
出力
Yes
足場 $3$ に着地する方法の一例を示します。
- はじめ、スタミナ $3$ 、高度 $0$ の状態で足場 $1$ にいる。
- 高度を $12$ 上げる。高度が $12$ になり、スタミナが $2$ になる。
- 足場 $2$ に移動する。
- 足場 $2$ に着地する。高度が $10$ になり、スタミナが $3$ になる。
- 高度を $12$ 上げる。高度が $22$ になり、スタミナが $2$ になる。
- 高度を $12$ 上げる。高度が $34$ になり、スタミナが $1$ になる。
- 足場 $3$ に移動する。
- 足場 $3$ に着地する。高度が $30$ になり、スタミナが $3$ になる。
サンプル2
入力
4 1 100 0 100 200 0
出力
Yes
スタミナが $0$ になることは許容されること、次の足場と同じ高度であれば移動できることに注意してください。
サンプル3
入力
10 5 1 1 0 0 0 0 0 0 0 0 7
出力
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。