Cod sursa(job #1037669)

Utilizator Tudordmdaniel marin Tudordm Data 20 noiembrie 2013 17:01:39
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<algorithm>

int h[100001],nh;

struct oaie{

    int dist;
    int lana;

}v[100001];

bool cmp(oaie a,oaie b){

    return a.dist>b.dist;

}

void schimba(int p1,int p2){

    int aux;
    aux=h[p1];
    h[p1]=h[p2];
    h[p2]=aux;
}

void urca(int p){

    while(p!=1&&h[p]<h[p/2]){
        schimba(p,p/2);
        p/=2;
    }
}

void adauga(int x){

    h[++nh]=x;
    urca(nh);
}

/*void coboara(int p){

    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh&&h[fs]<h[bun])
        bun=fs;
    if(fd<=nh&&h[fd]<h[bun])
        bun=fd;
    if(bun!=p){
        schimba(p,bun);
        coboara(bun);
    }
}
*/

void coboara(int poz){
    int aux, bun;
    while(2*poz <= h[0]){
        bun = poz;
        if(2*poz <= h[0] && h[bun] > h[poz*2]){
            bun = 2*poz;
        }
        if(2*poz+1 <= h[0] && h[bun] > h[poz*2+1]){
            bun = 2*poz + 1;
        }
        if(bun == poz) return;
        aux = h[poz];
        h[poz] = h[bun];
        h[bun] = aux;
        poz = bun;
    }
}

void sterge(int p){

    schimba(h[p],h[nh--]);
    urca(p);
    coboara(p);
}


int main(){

    int n,x,l,a,d,i,cont=0;
    long long total = 0;

    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

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

    for(i=1;i<=n;i++){

        scanf("%d%d",&d,&a);

        v[i].dist=d;
        v[i].lana=a;

    }
    std::sort(&v[1],&v[n+1],cmp);

    for(i=1;i<=n;i++){
        if(v[i].dist + cont <= x)
        {
            adauga(v[i].lana);
            total += v[i].lana;
            cont += l;
        }
        else
            if(v[i].lana > h[1])
            {
                total += v[i].lana - h[1];
                h[1] = v[i].lana;
                coboara(1);
            }
    }
    printf("%lld",total);
    return 0;
}