Cod sursa(job #221505)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 16 noiembrie 2008 18:12:58
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<stdio.h>

#define NMAX 100//000
struct bee{int d,a,g;};
bee v[NMAX+1];

void poz(int li,int ls,int &piv){
int i=li,j=ls,d=0;
bee aux;
while(i<j){
	if(v[i].a<v[j].a||
	   v[i].a==v[j].a&&v[i].g>v[j].a){
			aux=v[i];v[i]=v[j];v[j]=aux;d=1-d;
			}
	   i+=d;
	   j-=1-d;
	}
piv=i;
}
void qsrt(int st,int dr){
int piv;
if(st<dr){
	poz(st,dr,piv);
	qsrt(st,piv-1);
	qsrt(piv+1,dr);
	}
}


int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int n,x,l,gmax,rmax;
scanf("%d%d%d",&n,&x,&l);
gmax=x/l+1;
rmax=x%l;
if(rmax==0) rmax=l;
int i,j,k=n;
for(i=0;i<n;++i){
	scanf("%d%d",&v[i].d,&v[i].a);
	if(v[i].d>x) {i--;k--;continue;}
	v[i].g=(x-v[i].d)/l+1;
	}
n=k;
qsrt(0,n-1);
long long s=0L;
int max[NMAX+1]={0};
j=0;
int gr,uji[NMAX+1];
for(i=1;i<=gmax&&j<n;++i){
	if(v[j].g>i) max[i]=v[j].g,j++;
	else{
		if(max[gr]<v[i].g) max[gr]=v[i].g;

		}
	}


for(i=1;i<=gmax&&j<n;++i){
	if(v[j].g>i) s+=v[j].a,j++;
	else if(v[j].g==i) {
		s+=v[j].a;
		while(j<n&&v[j].g==i) j++;
		}
	}
printf("%lld",s);
return 0;
}