Cod sursa(job #1609786)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 23 februarie 2016 00:03:41
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <algorithm>
#define MAXN 100000
int s[MAXN], e[MAXN], u[MAXN], heap[MAXN], k;
bool cmp(const int x, const int y){
    return u[x]>u[y];
}
inline int tata(int p){
    return (p-1)/2;
}
inline int fiust(int p){
    return 2*p+1;
}
inline int fiudr(int p){
    return 2*p+2;
}
inline void swap(int a, int b){
    int aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
}
inline void coborare(int p){
    int q, f=1;
    while((f)&&(fiust(p)<k)){
        q=fiust(p);
        if((fiudr(p)<k)&&(heap[fiudr(p)]>heap[q])){
            q=fiudr(p);
        }
        if(heap[q]>heap[p]){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void urcare(int p){
    while((p>0)&&(heap[p]>heap[tata(p)])){
        swap(p, tata(p));
        p=tata(p);
    }
}
int main(){
    int n, x, l, i, j, a;
    long long ans;
    FILE *fin, *fout;
    fin=fopen("lupu.in", "r");
    fout=fopen("lupu.out", "w");
    fscanf(fin, "%d%d%d", &n, &x, &l);
    for(i=0; i<n; i++){
        fscanf(fin, "%d%d", &a, &s[i]);
        e[i]=i;
        u[i]=(x-a)/l;
    }
    std::sort(e, e+n, cmp);
    i=0;
    ans=0;
    k=0;
    x=u[0];
    while((i<n)&&(u[e[i]]!=0)){
        j=i;
        while((x>u[e[i]])&&(k>0)){
            ans+=heap[0];
            k--;
            heap[0]=heap[k];
            coborare(0);
            x--;
        }
        while(u[e[i]]==u[e[j]]){
            heap[k++]=s[e[i]];
            urcare(k-1);
            i++;
        }
        ans+=heap[0];
        k--;
        heap[0]=heap[k];
        coborare(0);
        x=u[e[j]];
    }
    while((x>0)&&(k>0)){
        ans+=heap[0];
        k--;
        heap[0]=heap[k];
        coborare(0);
        x--;
    }
    fprintf(fout, "%lld\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}