結果

問題 No.3459 Defeat Slimes
コンテスト
ユーザー yuunegi
提出日時 2026-02-28 14:50:26
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 528 ms / 3,000 ms
コード長 2,177 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,209 ms
コンパイル使用メモリ 348,432 KB
実行使用メモリ 17,076 KB
最終ジャッジ日時 2026-02-28 14:50:45
合計ジャッジ時間 17,867 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

int main(void){
    int n;
    long long y,z;
    cin>>n>>y>>z;
    priority_queue<pair<long long,pair<long long,long long>>>pq1;
    priority_queue<pair<long long,long long>>pq2;
    for(int i=0;i<n;i++){
        long long c,l,x;
        cin>>c>>l>>x;
        if(l<z)pq1.push({-l,{c,x}});
    }
    long long next=-pq1.top().first;
    while(!pq1.empty()){
        if(next<=y){
            pq2.push({pq1.top().second.second,pq1.top().second.first});
            pq1.pop();
            if(!pq1.empty()){
                next=-pq1.top().first;
            }else{
                next=z+1;
            }
        }else{
            break;
        }
    }
    long long sum=0;
    while(!pq2.empty()){
        long long xd=pq2.top().first,cd=pq2.top().second;
        if(next>z){
            if((z-y-1)/xd+1>=cd){
                y+=xd*cd;
                sum+=cd;
                pq2.pop();
            }else{
                sum+=(z-y-1)/xd+1;
                cout<<sum<<endl;
                return 0;
            }
        }else{
            if((next-y-1)/xd+1>=cd){
                y+=xd*cd;
                sum+=cd;
                pq2.pop();
            }else{
                sum+=(next-y-1)/xd+1;
                y+=((next-y-1)/xd+1)*xd;
                pq2.pop();
                pq2.push({xd,cd-((next-y-1)/xd+1)});
                if(y>=z){
                    cout<<sum<<endl;
                    return 0;
                }else{
                    while(!pq1.empty()){
                        if(next<=y){
                            pq2.push({pq1.top().second.second,pq1.top().second.first});
                            pq1.pop();
                            if(!pq1.empty()){
                                next=-pq1.top().first;
                            }else{
                                next=z+1;
                            }
                        }else{
                            break;
                        }
                    }
                }
            }
        }
        //cout<<y<<" "<<sum<<" "<<pq2.top().first<<" "<<pq2.top().second<<endl;
    }
    cout<<-1<<endl;
    return 0;
}
0