#1150061 (C++17) No.3459 Defeat Slimes

• 問題: No.3459 Defeat Slimes
• ユーザー: jupiter_68
• 提出日時: 2026-02-28 14:00:59
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,041 bytes
• コンパイル時間: 2,645 ms
• コンパイル使用メモリ: 235,240 KB
• 実行使用メモリ: 23,888 KB
• 最終ジャッジ日時: 2026-02-28 14:01:15
• 合計ジャッジ時間: 12,279 ms
• ジャッジサーバーID （参考情報）: judge7 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 20 WA * 10

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

struct Edge {
    ll from, to, cost;
    Edge (ll from, ll to, ll cost = 1ll) : from(from), to(to), cost(cost) {}
};
struct Graph {
    vector<vector<Edge>> G;
    Graph() = default;
    explicit Graph(ll N) : G(N) {}
    size_t size() const {
        return G.size();
    }
    void add(ll from, ll to, ll cost = 1ll, bool direct = 0) {
        G[from].emplace_back(from, to, cost);
        if (!direct) G[to].emplace_back(to, from, cost);
    }
    vector<Edge> &operator[](const int &k) {
        return G[k];
    }
};
using Edges = vector<Edge>;

const ll mod = 998244353; // 1000000007;

struct mint {
    ll x;
    mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    mint &operator+=(const mint &p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint &p) {
        x = (ll)(1ll * x * p.x % mod);
        return *this;
    }
    mint &operator/=(const mint &p) {
        *this *= p.inv();
        return *this;
    }
    mint operator-() const { return mint(-x); }
    mint operator+(const mint &p) const { return mint(*this) += p; }
    mint operator-(const mint &p) const { return mint(*this) -= p; }
    mint operator*(const mint &p) const { return mint(*this) *= p; }
    mint operator/(const mint &p) const { return mint(*this) /= p; }
    bool operator==(const mint &p) const { return x == p.x; }
    bool operator!=(const mint &p) const { return x != p.x; }
    friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
    friend istream &operator>>(istream &is, mint &a) {
        ll t; is >> t; a = mint(t); return (is);
    }
    mint inv() const { return pow(mod - 2); }
    mint pow(ll n) const {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
};

void solve(){
    ll N, Y, Z; cin >> N >> Y >> Z;
    vv<ll> a(N, vl(3));
    rep(i, N) cin >> a[i][2] >> a[i][0] >> a[i][1];
    sort(all(a));
    priority_queue<pll> pQ;
    vl b(N);
    rep(i, N) b[i] = a[i][0];
    b.push_back(8e18);
    ll ans = 0;
    rep(i, N){
        if(b[i] <= Y) pQ.push({a[i][1], a[i][2]});
    }
    ll ix = lower_bound(all(b), Y) - b.begin();
    while(Y < Z){
        if(pQ.empty()){
            cout << -1 << endl;
            return;
        }
        pll p = pQ.top(); pQ.pop();
        ll nx = min(Z, b[ix]);
        ll x = (nx - Y) / p.first + ((nx - Y) % p.first > 0);
        if(x <= p.second){
            Y += x * p.first;
            ans += x;
            if(x < p.second) pQ.push({p.first, p.second - x});
            if(nx == Z){
                cout << ans << endl;
                return;
            }else{
                while(b[ix] <= Y){
                    pQ.push({a[ix][1], a[ix][2]});
                    ix++;
                }
            }
        }else{
            Y += p.first * p.second;
            ans += p.second;
            continue;
        }
    }
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}