Cod sursa(job #325694)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 21 iunie 2009 22:50:57
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<stdio.h>

#define NM 100001
struct bee{int d,a;};
bee h[NM];
int n;

inline int tata(int k){return k/2;}
inline int fiu_st(int k){return k*2;}
inline int fiu_dr(int k){return k*2+1;}
inline int max(){return h[1].a;}

void sift(int k){
int fiu;
bee aux;
do{
	fiu=0;
	if(fiu_st(k)<=n) fiu=fiu_st(k);
	if(fiu_dr(k)<=n&&h[fiu_dr(k)].a>h[fiu_st(k)].a)
		fiu=fiu_dr(k);
	if(h[fiu].a<=h[k].a) fiu=0;
	if(fiu) aux=h[k],h[k]=h[fiu],h[fiu]=aux,k=fiu;
	}while(fiu);
}
void percolate(int k){
bee temp=h[k];
while(k>1&&temp.a>h[tata(k)].a) h[k]=h[tata(k)],k=tata(k);
h[k]=temp;
}
void clear(int k){
h[k]=h[n--];
if(n)
	if(k>1&&h[k].a>h[tata(k)].a) percolate(k);
	else sift(k);
}
void build_heap(){
int i;
for(i=n/2;i;--i) sift(i);
}

int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i,m,x,l,d,a;
scanf("%d%d%d",&m,&x,&l);
for(i=1;i<=m;++i){
	scanf("%d%d",&d,&a);
	if(h[i].d<=x) {++n,h[n].d=d,h[n].a=a;}
	}
build_heap();
long long s=0L;
while(n&&x>=0){
	if(h[1].d>x) clear(1);
	else {s+=h[1].a;x-=l;clear(1);}
	}
printf("%lld",s);
return 0;
}