Cod sursa(job #62270)

Utilizator swift90Ionut Bogdanescu swift90 Data 22 mai 2007 11:43:21
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<stdio.h>
#include<stdlib.h>
struct oi{
	int d,a,t;
};
int comp(const void*p,const void*q){
	oi *pp=(oi*)p,*qq=(oi*)q;
	oi px=*pp, py=*qq;
	if(px.t<py.t)
		return 1;
	if(px.t>py.t)
		return -1;
	return 0;
}
oi nr[100001];
int main(){
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int n,x,l,i,max,tmax,j,j1;
	int s;
	scanf("%d %d %d",&n,&x,&l);
	tmax=0;
	for(i=0;i<n;i++){
		scanf("%d %d",&nr[i].d,&nr[i].a);
		nr[i].t=(x-nr[i].d)/l;
		if(nr[i].t>tmax)
			tmax=nr[i].t;
	}
	
	qsort(nr,n,sizeof(nr[0]),comp);
	
	s=0;
	i=0;
	while((i<n)&&(tmax>-1)){
		max=0;
		j=0;
		while((nr[j].t>=tmax)&&(j<n)){
			if(nr[j].a>max){
				max=nr[j].a;
				j1=j;
			}
			j++;
		}
		s=s+max;
		tmax--;
		nr[j1].a=-1;
		i=j;
	}
	
	printf("%d\n",s);
	
	return 0;
}