提出 #67720539

---

ソースコード 拡げる

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

class Solution {
public:
    void solve() {

        u64 N; int M;
        cin>>N>>M;
        vector<pair<u64,u64>> V;
        V.reserve(M);
        for(int i=0;i<M;i++){
            u64 A,B;cin>>A>>B;
            if(A<=N) V.emplace_back(A,A-B);
        }
        sort(V.begin(),V.end());

        vector<pair<u64,u64>> heap;
        __uint128_t E=N;
        u64 ans=0;
        int i=0, K=V.size();

        auto cmp = [](auto &a, auto &b){ return a.second > b.second; };

        while(i<K && V[i].first<=E){
            heap.push_back(V[i++]);
            push_heap(heap.begin(), heap.end(), cmp);
        }
        while(!heap.empty()){
            pop_heap(heap.begin(), heap.end(), cmp);
            auto [A,C]=heap.back();
            heap.pop_back();
            if(E<A) continue;
            __uint128_t t=(E-A)/C+1;
            ans+=(u64)t;
            E-=t*C;
        }
        cout<<ans<<"\n";
    }
};

int main(){
    Solution *s=new Solution();
    s->solve();
    return 0;
}

提出情報

ジャッジ結果