Cod sursa(job #2415156)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 25 aprilie 2019 16:22:55
Problema Lupul Urias si Rau Scor 72
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int maxi,sol,X,n,L,t,i,h[100001],x,k;
struct meme{
    int l,t;
}v[100001];
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,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){
            h[++k]=i;
            i++;
            up_heap(k);
        }
        sol+=v[h[1]].l;
        swap(h[1],h[k]);
        k--;
        down_heap(1);
    }
    g<<sol;
    return 0;
}