Pagini recente » Cod sursa (job #288286) | Cod sursa (job #1971013) | Cod sursa (job #368407) | Cod sursa (job #43713) | Cod sursa (job #778296)
Cod sursa(job #778296)
#include<fstream>
#include<algorithm>
using namespace std;
struct sheep {int dist; int wool;};
int h[100002];
sheep v[100002];
int n,x,l,d,a,sum,sizeheap,step[100002],r,i,j,nrsteps,nrc,tmax;
char buff[100];
struct comp
{bool operator()(const sheep &a, const sheep &b) const
{
return (a.dist<b.dist);
}
};
void swap(int z1, int z2)
{int 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]<h[z])
{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]>h[2*z])
son=2*z+1;}
else
return;
if(h[z]<=h[son])
{swap(z,son);
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();
sheep q;
q.dist=d; q.wool=a;
v[i]=q;
if(((x-d)/l)>tmax)
tmax=(x-d)/l;
}
sort(v+1, v+n+1, comp());
i=1;
for(j=tmax; j>=0; j--)
{
while(((x-v[i].dist)/l)==j && i<=n) {sizeheap++; h[sizeheap]=v[i].wool; swim(sizeheap); i++;}
if(sizeheap)
{sum+=h[1];
swap(1,sizeheap);
sizeheap--;
sink(1);
}
}
printf("%d",sum);
return 0;
}