結果

問題 No.3459 Defeat Slimes
コンテスト
ユーザー InTheBloom
提出日時 2026-02-28 14:48:29
言語 D
(dmd 2.112.0)
コンパイル:
dmd -fPIE -m64 -w -wi -O -release -inline -I/opt/dmd/src/druntime/import/ -I/opt/dmd/src/phobos -L-L/opt/dmd/linux/lib64/ -fPIC _filename_
実行:
./Main
結果
AC  
実行時間 357 ms / 3,000 ms
コード長 2,369 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,211 ms
コンパイル使用メモリ 172,176 KB
実行使用メモリ 15,276 KB
最終ジャッジ日時 2026-02-28 14:48:47
合計ジャッジ時間 16,578 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import std;

void main () {
    int N;
    long Y, Z;
    readln.read(N, Y, Z);

    auto C = new long[](N);
    auto L = new long[](N);
    auto X = new long[](N);
    foreach (i; 0 .. N) {
        readln.read(C[i], L[i], X[i]);
    }

    // 倒した際のレベル上がり幅が最大のものを狙って倒すのが当然最適
    // 倒せるようになったスライムの集合を(上がり幅, 残り)で管理して頑張ると行ける？

    alias T = Tuple!(long, long);
    auto pq = BinaryHeap!(T[], "a[0] < b[0]")([]);

    auto ord = iota(N).array;
    ord.sort!((a, b) => L[a] < L[b]);

    int nextSlime = 0;

    long ans = 0;
    long curLevel = Y;
    while (true) {
        // スライム追加
        while (nextSlime < N && L[ord[nextSlime]] <= curLevel) {
            pq.insert(T(X[ord[nextSlime]], C[ord[nextSlime]]));
            nextSlime++;
        }

        if (pq.empty() || Z <= curLevel) {
            break;
        }
        auto top = pq.front();
        pq.removeFront();

        // 次のスライムを管理下におくまでの必要数
        long nextKill = long.max;
        if (nextSlime < N) {
            long v = max(0L, L[ord[nextSlime]] - curLevel);
            nextKill = (v + top[0] - 1) / top[0];
        }

        // Z以上までの必要数
        long goalKill = 0;
        {
            long v = max(0L, Z - curLevel);
            goalKill = (v + top[0] - 1) / top[0];
        }

        // どちらも無理な場合
        if (top[1] < goalKill && top[1] < nextKill) {
            curLevel += top[0] * top[1];
            ans += top[1];
            continue;
        }

        // スライム追加が優先の場合
        if (nextKill <= top[1] && nextKill < goalKill) {
            curLevel += top[0] * nextKill;
            ans += nextKill;
            top[1] -= nextKill;
            if (0 < top[1]) {
                pq.insert(top);
            }
            continue;
        }

        // 終わらせられる場合
        curLevel += top[0] * goalKill;
        ans += goalKill;
    }

    if (curLevel < Z) {
        writeln(-1);
    }
    else {
        writeln(ans);
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0