Cod sursa(job #2415187)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 25 aprilie 2019 16:43:27
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
long long X,n,L,t,i,h[100005],x,k,maxi,sol;
struct meme{
   int t,l;
}v[100005];

class compare{
public:
    bool operator ()(int a, int b){
        return a<b;
    }


};
priority_queue <int, vector<int>, compare> q;
int cmp(meme a,meme b){
    if(a.t==b.t)
        return a.l>b.l;
    return a.t>b.t;
}
void up_heap(int poz){
    while(poz/2>=1){
        if(v[h[poz]].l>v[h[poz/2]].l)
            swap(h[poz],h[poz/2]);
        else
            return;
        poz=poz/2;
    }
}
void down_heap(int poz){
    while(poz*2<=k){
        int st=poz*2;
        if(st+1<=k&&v[h[st]].l<v[h[st+1]].l)
            st++;
        if(v[h[poz]].l<v[h[st]].l)
            swap(h[poz],h[st]);
        else
            return;
        poz=st;
    }
}
int main()
{   f>>n>>X>>L;
    for(i=1;i<=n;i++){
        f>>x>>v[i].l;
        v[i].t=(X-x)/L+1;
        maxi=max(maxi,1ll*v[i].t);
    }
    sort(v+1,v+n+1,cmp);
    i=1;k=0;sol=0;
    for(t=maxi;t>=1;t--){
        while(v[i].t==t&&i<=n){
          /*  h[++k]=i;

            up_heap(k);*/
            q.push(v[i].l);
             i++;
        }
        if(!q.empty()){

          /*  sol+=v[h[1]].l;
            swap(h[1],h[k]);
            k--;
            down_heap(1);*/
            sol+=q.top();
            q.pop();
        }
    }
    g<<sol;
    return 0;
}