Pagini recente » Cod sursa (job #1654294) | Cod sursa (job #2177055) | Cod sursa (job #2822251) | Cod sursa (job #2722920) | Cod sursa (job #1412010)
#include<cstdio>
#include<algorithm>
using namespace std;
struct oaie{
long long d;
long long a;
}v[200100];
long long n,x,l,dh,i,j,nr,h[200100];
long long s;
FILE *f,*g;
long long cmp(oaie a,oaie b){
return a.d<b.d;
}
void chg(long long &a,long long &b){
long long aux=a;
a=b;
b=aux;
}
void heapins(long long n){
long long c=dh;
long long p=dh/2;
while(p>=1){
if(v[ h[c] ].a > v[ h[p] ].a){
chg(h[c],h[p]);
c=p;
p/=2;
}
else
break;
}
}
void heapdel(){
long long p=1;
long long c=2;
while(c<=dh){
if( v[ h[c] ].a < v[ h[c+1] ].a && c+1<=dh )
c++;
if( v[ h[c] ].a > v[ h[p] ].a ){
chg(h[c],h[p]);
p=c;
c*=2;
}
else
break;
}
}
int main(){
f=fopen("lupu.in","r");
g=fopen("lupu.out","w");
fscanf(f,"%lld%lld%lld",&n,&x,&l);
for(i=1;i<=n;i++){
fscanf(f,"%lld%lld",&v[i].d,&v[i].a);
}
sort(v+1,v+n+1,cmp);
nr=1;
for(i=0;i<=x;i+=l){
while(v[nr].d<=i&&nr<=n){
dh++;
h[dh]=nr;
heapins(nr);
nr++;
}
if(!dh)
continue;
s+=v[ h[1] ].a;
chg(h[1],h[dh]);
dh--;
heapdel();
}
fprintf(g,"%lld",s);
fclose(f);
fclose(g);
return 0;
}