結果

問題 No.2922 Rose Garden
コンテスト
ユーザー yamasaKit_
提出日時 2025-01-31 23:34:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 202 ms / 3,000 ms
コード長 2,488 bytes
コンパイル時間 4,183 ms
コンパイル使用メモリ 280,328 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-31 23:34:54
合計ジャッジ時間 10,768 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

static const long long NEG_INF = -1000000000000000000LL; // 十分小さい値(負の無限大の代用)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, S, B;
    cin >> N >> S >> B;

    vector<long long> H(N);
    for(int i=0; i<N; i++){
        cin >> H[i];
    }

    // dp[j] : 今の足場にいるときスタミナが j の場合に到達できる最大の高さ
    vector<long long> dp(S+1, NEG_INF);
    dp[S] = H[0]; // 最初は足場0にスタミナSでいるので、その高さを初期値とする

    // N個の足場のうち、1～N-1の足場に移動していく
    for(int i=1; i<N; i++){
        vector<long long> dp2(S+1, NEG_INF);
        long long hi = H[i];
        bool reachable = false; // この足場に到達できるかどうか

        // j: 現在のスタミナ
        for(int j=S; j>=0; j--){
            long long currentHeight = dp[j];
            if(currentHeight == NEG_INF) {
                continue; // そもそも到達できていない場合はスキップ
            }

            // dp[j] >= hi の場合はスタミナを消費せずそのまま移れる
            if(currentHeight >= hi) {
                dp2[j] = max(dp2[j], currentHeight);
                reachable = true;
            } else {
                // 足りない高さをBずつ上げて hi 以上にするためのスタミナ消費量
                long long diff = hi - currentHeight;
                // used_s = ceil(diff / B)
                long long used_s = (diff + B - 1) / B; 
                if(j >= used_s){
                    // used_sだけスタミナを消費して高さを上げる
                    long long newHeight = currentHeight + used_s * B;
                    dp2[j - used_s] = max(dp2[j - used_s], newHeight);
                    reachable = true;
                }
            }
        }
        // 足場iに到達できるなら、そこからスタミナをSに回復しつつ高さをhiに降りる
        // (Pythonの実装に合わせ、dp2[S]とhiの大小比較でmaxを取っている)
        if(reachable) {
            dp2[S] = max(dp2[S], hi);
        }

        dp = dp2;
    }

    // dpの中にNEG_INFより大きい値が1つでもあれば到達可能
    long long maxVal = *max_element(dp.begin(), dp.end());
    if(maxVal > NEG_INF){
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}
0