Cod sursa(job #1798719)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 5 noiembrie 2016 13:03:59
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <stdio.h>
#include <stdlib.h>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXN 1000000
class A{
    public:
    long long val[MAXN+1], val2[MAXN+1];
    int pos[MAXN+1];
    int heap[MAXN+1], last;

    inline int Heap_father(int p){
        return p/2;
    }
    inline int Heap_leftson(int p){
        return 2*p;
    }
    inline int Heap_rightson(int p){
        return 2*p+1;
    }
    inline void Heap_Swap(int p1, int p2){
        pos[heap[p1]]=p2;
        pos[heap[p2]]=p1;
        int aux=heap[p1];
        heap[p1]=heap[p2];
        heap[p2]=aux;
    }
    inline void Heap_upheap(int p){
        while(Heap_father(p)>0 && val[heap[p]]>val[heap[Heap_father(p)]]){
            Heap_Swap(p, Heap_father(p));
            p=Heap_father(p);
        }
    }
    inline void Heap_downheap(int p){
        int flag=1;
        int ts=-1;
        while(flag){
            ts=-1;
            if(Heap_leftson(p)>last)
                flag=0;
            else{
                if(val[heap[Heap_leftson(p)]]>val[heap[p]])
                    ts=Heap_leftson(p);
                if(Heap_rightson(p)<=last && val[heap[Heap_rightson(p)]]>val[heap[Heap_leftson(p)]] && val[heap[Heap_rightson(p)]]>val[heap[p]])
                    ts=Heap_rightson(p);
                if(ts==-1)
                    flag=0;
                else{
                    Heap_Swap(p, ts);
                    p=ts;
                }
            }
        }
    }
    inline void Heap_insert(int poz){
        heap[++last]=poz;
        pos[poz]=last;
        Heap_upheap(last);
    }
    inline void Heap_erase(int poz){
        int p=pos[poz];
        Heap_Swap(p, last);
        last--;
        if(Heap_father(p)>0 && val[heap[p]]>val[heap[Heap_father(p)]])
            Heap_upheap(p);
        else
            Heap_downheap(p);
    }
} H1;

inline long long max(long long a, long long b){
    return a > b ? a : b;
}

int main(){
    fi=fopen("lupu.in","r");
    fo=fopen("lupu.out","w");
    int n=nextnum();
    long long x=nextnum(), l=nextnum();
    for(int i=1;i<=n;i++){
        H1.val2[i]=nextnum();
        H1.val[i]=nextnum();
        H1.Heap_insert(i);
    }
    //printf("%d ", H1.heap[1]);
    int chosen=0;
    long long sum=0LL;
    while(H1.last>0){
        while(H1.last>0 && H1.val2[H1.heap[1]]+l*chosen>x)
            H1.Heap_erase(H1.heap[1]);
        //printf("%d ", H1.heap[1]);
        chosen++;
        if(H1.last>0){
            sum+=H1.val[H1.heap[1]];
            H1.Heap_erase(H1.heap[1]);
        }
    }
    fprintf(fo,"%lld", sum);
    fclose(fi);
    fclose(fo);
    return 0;
}