Pagini recente » Cod sursa (job #119324) | Cod sursa (job #654907) | Istoria paginii runda/lotul_pestisorilor | Cod sursa (job #1757011) | Cod sursa (job #218193)
Cod sursa(job #218193)
#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;
}