Pagini recente » Cod sursa (job #2955613) | Cod sursa (job #1643660) | Cod sursa (job #2405248) | Cod sursa (job #3230322) | Cod sursa (job #778146)
Cod sursa(job #778146)
#include<fstream>
using namespace std;
struct sheep {int dist; int wool;};
sheep h[100002];
int n,x,l,d,a,sum,sizeheap,step[100002],r,i;
void swap(int z1, int z2)
{sheep aux=h[z1];
h[z1]=h[z2];
h[z2]=aux;
}
void swim(int z)
{int father;
do{father=0;
if((z/2)>=1)
father=z/2;
else
return;
if(h[father].wool<h[z].wool)
{swap(father,z);
z=father;}
else
{if(h[father].wool==h[z].wool && h[father].dist<h[z].dist)
{swap(father,z);
z=father;}
else
father=0;}
}while(father);
}
void sink(int z)
{int son;
do{son=0;
if(2*z<=sizeheap)
{son=2*z;
if(2*z+1<=sizeheap && (h[2*z+1].wool>h[2*z].wool || (h[2*z+1].wool==h[2*z].wool && h[2*z+1].dist>h[2*z].dist)))
son=2*z+1;}
else
return;
if(h[z].wool<h[son].wool)
{swap(z,son);
z=son;}
else
{if(h[son].wool==h[z].wool && h[son].dist>h[z].dist)
{swap(son,z);
z=son;}
else
son=0;}
}while(son);
}
int main()
{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,&a);
sizeheap++;
sheep q;
q.dist=d; q.wool=a;
h[sizeheap]=q;
swim(sizeheap);}
while(sizeheap)
{r=((x-h[1].dist)/l)+1;
if(step[r]==0)
{step[r]=1;
sum+=h[1].wool;}
swap(1,sizeheap);
sizeheap--;
sink(1);
}
printf("%d",sum);
return 0;
}