Cod sursa(job #1254518)

Utilizator livliviLivia Magureanu livlivi Data 2 noiembrie 2014 20:45:06
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<algorithm>
#include<cstdio>
#define MAX 100000
using namespace std;

struct mazi{int dist,lana;};

int h[2*MAX+1];
int last;

mazi v[MAX+1];

int meow(mazi a,mazi b){
    if (a.dist<b.dist) return true;
    return false;
}


void schimba (int poz1,int poz2){
    int aux;
    aux=h[poz1];
    h[poz1]=h[poz2];
    h[poz2]=aux;
}


void sterge(){
    if (last==1){
        last=0;
        h[1]=0;
        return ;
    }

    schimba (1,last);
    last--;

    int x;
    x=1;
    int fl=1;

    while(x<=last &&fl==1){
        if (h[x*2]>h[x] &&h[x*2]>=h[x*2+1] &&x*2<=last){
            schimba (x,x*2);
            x=x*2;
        }
        else
        if (h[x*2+1]>h[x] &&h[x*2+1]>=h[x*2] &&x*2+1<=last){
            schimba (x,x*2+1);
            x=x*2+1;
        }
        else fl=0;
    }
}


void adauga(int x){
    last++;
    h[last]=x;

    x=last;

    while(h[x]>h[x/2] &&x>1){
        schimba(x,x/2);
        x/=2;
    }
}

int main(){
    freopen ("lupu.in","r",stdin);
    freopen ("lupu.out","w",stdout);
    int n,x,l,i,j,m;
    long long slana;

    scanf ("%d%d%d",&n,&x,&l);

    for(i=1;i<=n;i++)
        scanf ("%d%d",&v[i].dist,&v[i].lana);

    sort(v+1,v+n+1,meow);

    slana=0;
    j=1;
    last=0;

    for(i=0;i<=x;i+=l){
        m=i+(x%l);
        for(;v[j].dist<=m &&j<=n;j++)
            adauga(v[j].lana);
        slana=slana+h[1];
        sterge();
    }

    printf ("%lld",slana);

    return 0;
}