Cod sursa(job #218193)

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

#define NMAX 100000
struct bee{int d,a;};
bee v[NMAX+1];

void poz(int li,int ls,int&piv){
int i=li,j=ls,d=0;
bee t;
while(i<j){
	if(v[i].d>v[j].d||
	   v[i].d==v[j].d&&v[i].a<v[j].a){
			t=v[i];v[i]=v[j];v[j]=t;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;
scanf("%d%d%d",&n,&x,&l);
int i,j,k;
for(i=0;i<n;++i)
	scanf("%d%d",&v[i].d,&v[i].a);
qsrt(0,n-1);
int s=0,max,mij,p,ok;
i=0,j=n-1,p=0,ok=0;
do{
	mij=(i+j)/2;
	if(x==v[mij].d) {p=mij;ok=1;}
	else if(x<v[mij].d) j=mij-1;
		 else i=mij+1;
	}while(!ok);
if(ok){
	while(p<n&&v[i].d<=x) p++;
	if(p==n) p=n-1;
	}
else if(x<v[mij].d){
		p=mij;
		while(p<n&&v[i].d<=x) p++;
		if(p==n) p=n-1;
		}
	 else{
		p=mij;
		while(p>0&&v[i].d>x) p--;
		if(p<0) p=0;
		}
k=x/l;
max=v[p].a;
for(i=p;i>=0;--i){
	j=i;
	while(v[j].d>(k-1)*l&&j>=0){
		if(max<v[j].a) max=v[j].a;
		j--;
		}
	s+=max;k--;
	i=j+1;max=v[j].a;
	}
printf("%d",s);
return 0;
}