Cod sursa(job #169422)

Utilizator MirageRobert Sandu Mirage Data 1 aprilie 2008 18:04:20
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<stdio.h>
#include<stdlib.h>
int comp(const void *a,const void *b){
	int *aa=(int *)a, *bb=(int *)b;
	int x=*aa, y=*bb;
	return x-y;
}
struct muie{
	int t,a,b;
};
muie v[100000];
inline void schimb(int &x,int &y){
	int aux;
	aux=x;
	x=y;
	y=aux;
}
void down(int i,int k,int *h){
	int max=i;
	if(i*2<=k&&h[max]<h[2*i])
		max=2*i;
	if(2*i+1<=k&&h[max]<h[2*i+1])
		max=2*i+1;
	if(i!=max){
		schimb(h[i],h[max]);
		down(max,k,h);
	}
}
void construieste(int n,int *h){
	for(int i=n/2;i>0;--i)
		down(i,n,h);
}
int main () {
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int n,x,l,i,act,max=-1,s=0,h[100000],q;
	scanf("%d%d%d",&n,&x,&l);
	for(i=0;i<n;++i){
		scanf("%d%d",&v[i].a,&v[i].b);
		if(v[i].a<=x){
			v[i].t=(x-v[i].a)/l;
			if(v[i].t>max)
				max=v[i].t;
		}
	}
	qsort(v,n,sizeof(v[0]),comp);
	act=v[n-1].t;
	q=1;
	for(i=n-1;i>=0;){
		while(v[i].t==act){
			h[q++]=v[i].b;
			--i;
		}
		act=v[i].t;
		construieste(n-i-1,h);
		s+=h[1];
		h[1]=0;
	}
	printf("%d\n",s);
	return 0;
}