#1150960 (C++23) No.3459 Defeat Slimes

• 問題: No.3459 Defeat Slimes
• ユーザー: Tatsu_mr
• 提出日時: 2026-03-01 23:53:11
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 122 ms / 3,000 ms
• コード長: 4,155 bytes
• コンパイル時間: 4,999 ms
• コンパイル使用メモリ: 346,516 KB
• 実行使用メモリ: 18,828 KB
• 最終ジャッジ日時: 2026-03-01 23:58:23
• 合計ジャッジ時間: 12,869 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

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

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()
#define SZ(v) ((int)(v).size())

using lint = long long;
using ld = long double;

const int INF = 1001001001;
const lint LINF = 1000000000000000000;
// 真上から反時計回り
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int di8[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false); cin.tie(nullptr);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} setupio;

namespace tatsumr {

template <class T>
bool chmin(T &a, const T &b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
bool chmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0; 
}
template <class T>
T mypow(T a, T b) {
    T res = 1;
    while (b) {
        if (b & 1) { res *= a; }
        a *= a; b >>= 1;
    }
    return res;
}
template <class T>
T modpow(T a, T b, T mod) {
    T res = 1;
    while (b) {
        if (b & 1) { res = (res * a) % mod; }
        a = (a * a) % mod; b >>= 1;
    }
    return res;
}

} // namespace tatsumr

using namespace tatsumr;

struct Slime {
    lint C, L, X;
    Slime(lint _C, lint _L, lint _X) : C(_C), L(_L), X(_X) {}
    bool operator<(const Slime &rhs) const {
        return X < rhs.X;
    }
    bool operator>(const Slime &rhs) const {
        return X > rhs.X;
    }
};

lint Need(const lint x, const lint y) {
    lint res = x / y;
    if (x % y != 0) res++;
    return res;
}

int main() {
    int N;
    lint Y, Z;
    cin >> N >> Y >> Z;
    vector<Slime> slimes;
    rep(i, N) {
        lint C, L, X;
        cin >> C >> L >> X;
        slimes.emplace_back(Slime(C, L, X));
    }
    sort(ALL(slimes), [](const Slime &lhs, const Slime &rhs) {
        return lhs.L <= rhs.L;
    });
    priority_queue<Slime> pq; // 倒せるスライム
    int i = 0;
    while (i < N && slimes[i].L <= Y) {
        pq.emplace(slimes[i]);
        i++;
    }
    lint ans = 0;
    while (!pq.empty()) {
        auto s = pq.top();
        pq.pop();
        // 1. 全種のスライムがpqに入っている場合...sをひたすら倒す
        if (i == N) {
            lint need = Need(Z - Y, s.X); // Zになるために最低何匹倒す必要があるか
            // 1-1. Zに到達できる場合
            if (s.C >= need) {
                ans += need;
                cout << ans << "\n";
                return 0;
            }
            // 1-2. まだZ以上にはならない場合
            else {
                Y += s.X * s.C;
                ans += s.C;
            }
        }
        // 2. まだpqに入れていないスライムがいる場合...ギリギリまでレベル上げ
        else {
            lint nl = slimes[i].L;
            lint need = Need(nl - Y, s.X); // 次のスライムが攻撃可能になるために最低何匹倒す必要があるか
            // 2-0. need匹以内でZに到達できる場合
            lint goal = Need(Z - Y, s.X);
            if (s.C >= need && need >= goal) {
                ans += goal;
                cout << ans << "\n";
                return 0;
            }
            // 2-1. sがneed匹以上いる場合...need匹倒して、次のスライムを入れる
            else if (s.C >= need) {
                // 倒す
                Y += s.X * need;
                ans += need;
                if (s.C > need) {
                    pq.emplace(Slime(s.C - need, s.L, s.X));
                }
                // 倒せるようになったスライムを入れる
                while (i < N && slimes[i].L <= Y) {
                    pq.emplace(slimes[i]);
                    i++;
                }
            }
            // 2-2. sがneed匹未満のとき...全員倒す
            else {
                Y += s.X * s.C;
                ans += s.C;
            }
        }
    }
    cout << -1 << "\n";
}