Cod sursa(job #2428744)

Utilizator mihai2003LLL LLL mihai2003 Data 6 iunie 2019 11:29:28
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>

struct oaie{
    int d,l;
    bool operator < (const oaie & aux)const{
        if(l==aux.l)
            return d<aux.d;
        return l>aux.l;
    }
}auxx;

long long suma=0;
std::ifstream in("lupu.in");
std::ofstream out("lupu.out");
std::vector<oaie>v;
std::priority_queue<int,std::vector<int>,std::greater<int> > pq,pq2;

int main(){
    int n,x,l;
    in>>n>>x>>l;
    for(int i=1;i<=n;i++)
        in>>auxx.d>>auxx.l,v.push_back(auxx);
    std::sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        if(v[i].d+suma<=x)
            suma+=l,pq.push(v[i].l);
        else{
            int cnt=0,last=0;
            pq2=pq;
            long long  sumad=0;
            while(!pq2.empty() && sumad<=v[i].l && v[i].d+suma-cnt*l>x)
                sumad+=pq2.top(),pq2.pop(),cnt++;
            cnt--;
            if(cnt>0 && v[i].d+suma-cnt*l<=x){
                suma-=cnt*l;
                for(int j=1;j<=cnt;j++)
                    pq.pop();
                pq.push(v[i].l);
                suma+=l;
            }
        }
    }
    long long  sumax=0;
    while(!pq.empty())
        sumax+=pq.top(),pq.pop();
    out<<sumax;
    return 0;
}