Cod sursa(job #1037804)

Utilizator Tudordmdaniel marin Tudordm Data 20 noiembrie 2013 19:12:19
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 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(fd<=nh&&h[fd]<h[bun])
        bun=fd;
    if(fs<=nh&&h[fs]<h[bun])
        bun=fs;
    if(bun!=p){
        schimba(p,bun);
        coboara(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 + l*cont <= x)
        {
            adauga(v[i].lana);
            total += v[i].lana;
            cont++;
        }
        else
            if(v[i].lana > h[1])
            {
                total += v[i].lana;
                total -= h[1];
                h[1] = v[i].lana;
                coboara(1);
            }
    }
    printf("%lld",total);
    return 0;
}