結果

問題 No.2922 Rose Garden
コンテスト
ユーザー yamasaKit_
提出日時 2025-01-31 23:31:58
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,498 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 197,376 KB
最終ジャッジ日時 2025-01-31 23:33:29
合計ジャッジ時間 90,098 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 TLE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import *
from itertools import *
from functools import cache, partial
from pprint import pprint
import sys
from typing import Any, Final

try:
    from icecream import ic
except ImportError:  # Graceful fallback if IceCream isn't installed.
    ic = lambda *a: None if not a else (a[0] if len(a) == 1 else a)  # noqa
debug = partial(print, file=sys.stderr)
dpprint = partial(pprint, stream=sys.stderr)
sys.setrecursionlimit(10**6)
MOD = 998244353

N, S, B = map(int, input().split())
H: Final[list[int]] = list(map(int, input().split()))

# dp([i])[j] := i 番目の足場にいるときにスタミナが j である時の最大の高さ
INF = float("inf")
dp = [-INF] * (S + 1)
dp[S] = H[0]
# ic(dp)

for i in range(1, N):
    dp2 = [-INF] * (S + 1)
    hi = H[i]
    reachable = False
    for j in reversed(range(S + 1)):
        if dp[j] >= hi:
            # そのままの高さを維持する
            dp2[j] = max(dp2[j], dp[j])
            reachable = True
        else:
            diff = hi - dp[j]
            # スタミナ 1 消費して高さを B 増やすのを繰り返し hi 以上にする
            used_s = (diff + B - 1) // B
            if j >= used_s:
                dp2[j - used_s] = max(dp2[j - used_s], used_s * B + dp[j])
                reachable = True
    # スタミナを回復しつつ hi に降りる
    if reachable:
        dp2[S] = max(dp2[S], hi)

    dp = dp2
    # ic(dp)

if max(dp) != -INF:
    print("Yes")
else:
    print("No")
0