Pagini recente » Cod sursa (job #2338216) | Cod sursa (job #2767007) | Cod sursa (job #910759) | Cod sursa (job #682612) | Cod sursa (job #1412005)
#include<cstdio>
#include<algorithm>
using namespace std;
struct oaie{
int d;
int a;
}v[100100];
int n,x,l,dh,i,j,s,nr,h[100100];
FILE *f,*g;
int cmp(oaie a,oaie b){
return a.d<b.d;
}
void chg(int &a,int &b){
int aux=a;
a=b;
b=aux;
}
void heapins(int n){
int c=dh;
int p=dh/2;
while(p>=1){
if(v[ h[c] ].d < v[ h[p] ].d){
chg(h[c],h[p]);
c=p;
p/=2;
}
else
break;
}
}
void heapdel(){
int p=1;
int c=2;
while(c<=dh){
if( v[ h[c] ].d < v[ h[c+1] ].d && c+1<=dh )
c++;
if( v[ h[c] ].d < v[ h[p] ].d ){
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,"%d%d%d",&n,&x,&l);
for(i=1;i<=n;i++){
fscanf(f,"%d%d",&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++;
}
s+=v[ h[1] ].a;
chg(h[1],h[dh]);
dh--;
heapdel();
}
fprintf(g,"%d",s);
fclose(f);
fclose(g);
return 0;
}