Pagini recente » Cod sursa (job #1844266) | Cod sursa (job #272250) | Cod sursa (job #1380161) | Cod sursa (job #3161692) | Cod sursa (job #1665390)
#include <cstdio>
#define MAXN 100000
int D[MAXN],A[MAXN];
inline void swap(int b,int e,int *v){
int aux=v[b];
v[b]=v[e];
v[e]=aux;
}
void myqsort(int begin,int end){
int b=begin,e=end,pivot=D[(b+e)/2];
while(b<=e){
while(D[b]<pivot) b++;
while(D[e]>pivot) e--;
if(b<=e){
swap(b,e,D);
swap(b,e,A);
b++;e--;
}
}
if(begin<e) myqsort(begin,e);
if(b<end) myqsort(b,end);
}
int Hl[MAXN];
inline int lson(int nod){
return 2*nod+1;
}
inline int rson(int nod){
return 2*nod+2;
}
inline int tata(int nod){
return (nod-1)/2;
}
inline void urcare(int nod){
while(nod>0&&Hl[nod]>Hl[tata(nod)]){
swap(nod,tata(nod),Hl);
nod=tata(nod);
}
}
inline void coborare(int nod,int n){
int aux,flag=1;
while(nod<n&&flag){
aux=nod;
if(lson(nod)<n&&Hl[nod]<Hl[lson(nod)])
aux=lson(nod);
if(rson(nod)<n&&Hl[aux]<Hl[rson(nod)])
aux=rson(nod);
if(nod==aux)
flag=0;
swap(nod,aux,Hl);
nod=aux;
}
}
int main(){
FILE*fi,*fout;
int i,n,x,l,nh,j,max,pas;
long long s;
fi=fopen("lupu.in" ,"r");
fout=fopen("lupu.out" ,"w");
fscanf(fi,"%d%d%d" ,&n,&x,&l);
for(i=0;i<n;i++)
fscanf(fi,"%d%d" ,&D[i],&A[i]);
myqsort(0,n-1);
max=0;
for(i=0;i<n;i++){
if(x<D[i])
D[i]=-1;
else
D[i]=(x-D[i])/l;
if(D[i]>max)
max=D[i];
}
i=nh=s=0;
pas=max;
while(i<n&&pas>=0){
j=i;
while(j<n&&D[j]==pas){
Hl[nh++]=A[j];
j++;
urcare(nh-1);
}
if(nh>0){
s=s+Hl[0];
Hl[0]=Hl[nh-1];
nh--;
coborare(0,nh);
}
i=j;
pas--;
}
fprintf(fout,"%lld" ,s);
fclose(fi);
fclose(fout);
return 0;
}