結果

問題 No.2922 Rose Garden
ユーザー yamasaKit_
提出日時 2025-01-31 23:31:29
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,498 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 52,660 KB
最終ジャッジ日時 2025-01-31 23:34:17
合計ジャッジ時間 166,171 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 TLE * 36
権限があれば一括ダウンロードができます

ソースコード

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