Pagini recente » Cod sursa (job #1269608) | Cod sursa (job #820691) | Cod sursa (job #362239) | Cod sursa (job #647332) | Cod sursa (job #778153)
Cod sursa(job #778153)
#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,nrsteps,nrc;
char buff[100];
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 get_number()
{int nrn=0;
while(buff[nrc]<='9' && buff[nrc]>='0')
{nrn=10*nrn+buff[nrc]-'0';
nrc++;}
return nrn;
}
int main()
{freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
gets(buff);
nrc=0;
n=get_number();
nrc++;
x=get_number();
nrc++;
l=get_number();
for(i=1; i<=n; i++)
{gets(buff);
nrc=0;
d=get_number();
nrc++;
a=get_number();
sizeheap++;
sheep q;
q.dist=d; q.wool=a;
h[sizeheap]=q;
swim(sizeheap);}
nrsteps=x/l+1;
while(nrsteps && sizeheap)
{r=((x-h[1].dist)/l)+1;
while(r>0 && step[r]==1) r--;
if(r>0 && step[r]==0)
{step[r]=1;
sum+=h[1].wool;
nrsteps--;
}
swap(1,sizeheap);
sizeheap--;
sink(1);
}
printf("%d",sum);
return 0;
}