Pagini recente » Cod sursa (job #2015384) | Cod sursa (job #252440) | Cod sursa (job #50164) | Cod sursa (job #242572) | Cod sursa (job #337574)
Cod sursa(job #337574)
#include <stdio.h>
#define Nmax 120000
#define INF 2000000000
#define ll long long
int h[Nmax],poz[Nmax],d[Nmax],a[Nmax],t[Nmax];
int n,x,l,dh;
ll sum;
void sort(int l,int r){
int i,j,x,y;
i=l; j=r; x=t[l+(r-l)/2];
do{
while(t[i] > x) i++;
while(x > t[j]) j--;
if(i<=j){
y=t[i]; t[i]=t[j]; t[j]=y;
y=d[i]; d[i]=d[j]; d[j]=y;
y=a[i]; a[i]=a[j]; a[j]=y;
i++; j--;
}
} while(i<=j);
if(i<r) sort(i,r);
if(l<j) sort(l,j);
}
void read(){
int i;
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for(i=1;i<=n;++i) scanf("%d%d",&d[i],&a[i]);
for(i=1;i<=n;++i)
if(d[i] > x) t[i]=-INF;
else t[i]=(x-d[i])/l;
sort(1,n);
// for(i=1;i<=n;++i) poz[i]=i;
}
void swap(int i,int j){
int aux=h[i]; h[i]=h[j];
h[j]=aux;
poz[h[i]]=i;
poz[h[j]]=j;
}
void UP(int k){
int tata=k/2;
if(tata)
if(a[h[k]] > a[h[tata]]){
swap(k,tata);
UP(tata);
}
}
void DOWN(int k){
int st=2*k,dr=st+1,max=k;
if(st<=dh && a[h[st]]>a[h[max]]) max=st;
if(dr<=dh && a[h[dr]]>a[h[max]]) max=dr;
if(max != k){
swap(k,max);
DOWN(max);
}
}
void work(){
int i,j,pmin;
j=1;
for(i=t[1]; i>=0; --i){
if(t[j] == i){
while(t[j] == i && j<=n){
++dh;
h[dh]=j;
poz[dh]=dh;
UP(poz[dh]);
++j;
}
// scot max
if(dh){
swap(1,dh);
dh--;
DOWN(1);
pmin=h[dh+1];
sum += a[pmin];
}
}
else
if(dh){
// scot max
swap(1,dh);
dh--;
DOWN(1);
pmin=h[dh+1];
sum += a[pmin];
}
}
printf("%lld\n",sum);
fclose(stdin); fclose(stdout);
}
int main(){
read();
work();
return 0;
}