結果

問題 No.2860 Heal Slimes
ユーザー dyktr_06
提出日時 2025-04-18 15:55:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,144 bytes
コンパイル時間 2,451 ms
コンパイル使用メモリ 196,544 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-18 15:56:07
合計ジャッジ時間 9,083 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

    int T;
    cin >> T;
    while(T--){
        int N, K;
        ll X;
        cin >> N >> K >> X;
        vector<ll> H(N);
        for(auto &h: H) cin >> h;

        // 1) mod X が揃っているかチェック
        ll r = H[0] % X;
        bool ok = true;
        for(int i = 1; i < N; i++){
            if(H[i] % X != r){
                ok = false;
                break;
            }
        }
        if(!ok){
            cout << "No\n";
            continue;
        }

        // 2) K == N の特別ケース
        if(K == N){
            // 全部同じじゃないとダメ
            bool all_eq = true;
            for(int i = 1; i < N; i++){
                if(H[i] != H[0]){
                    all_eq = false;
                    break;
                }
            }
            cout << (all_eq ? "Yes\n" : "No\n");
            continue;
        }

        // 3) 貪欲スライディングウィンドウ
        ll target = *max_element(H.begin(), H.end());
        vector<ll> add(N+1, 0);  // add[i] が i 項で curr に加わる量の変化
        ll curr = 0;             // 今までの操作によって項 i に加わった回数の累積

        bool fail = false;
        for(int i = 0; i < N; i++){
            curr += add[i];
            // 現在の体力
            ll curH = H[i] + curr * X;
            if(curH > target){
                fail = true;
                break;
            }
            ll need = (target - curH) / X;  // 追加で打つべき魔法回数
            if(i + K <= N){
                // まだ窓をスタートできる位置
                if(need > 0){
                    curr += need;
                    add[i+K] -= need;
                }
            } else {
                // 末尾: もう新たな魔法は打てない
                if(need != 0){
                    fail = true;
                    break;
                }
            }
        }
        cout << (fail ? "No\n" : "Yes\n");
    }

    return 0;
}
0