Pagini recente » Cod sursa (job #1742391) | Cod sursa (job #1324373) | Cod sursa (job #320417) | Cod sursa (job #2216638) | Cod sursa (job #330544)
Cod sursa(job #330544)
#include<stdio.h>
#include<stdlib.h>
#define Nmx 100001
#define Mare 100000001
int L[Nmx],n,X,l;
int H[Nmx],k,T[Nmx],Tmx;
int *Tf[Mare];
void citire()
{
scanf("%d%d%d",&n,&X,&l);
int x;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x,&L[i]);
if(X>=x)
{
T[i]=(X-x)/l+1;
if(T[i]>Tmx)
Tmx=T[i];
}
}
}
void initi()
{
for(int i=1;i<=Tmx;++i)
{
Tf[i]=(int *)realloc(Tf[i],sizeof(int));
Tf[i][0]=0;
}
for(int i=1;i<=n;++i)
{
if(T[i]!=0)
{
int j=i;
i=T[i];
Tf[i][0]++;
Tf[i]=(int *)realloc(Tf[i],(Tf[i][0]+1)*sizeof(int));
Tf[i][Tf[i][0]]=L[j];
i=j;
}
}
}
void upheap(int k)
{
while(k>1)
{
if(H[k]>H[k/2])
{
int t=H[k];
H[k]=H[k/2];
H[k/2]=t;
k=k/2;
}
else return;
}
}
void downheap(int K)
{
int t;
while(K<=k)
{
if(K*2<=k)
{
t=K*2;
if(K*2+1<=k)
if(H[t+1]>H[t])
++t;
}
else return;
if(H[K]<H[t])
{
int x=H[K];
H[K]=H[t];
H[t]=x;
K=t;
}
else return ;
}
}
void solve()
{
long long sol=0;
for(int i=Tmx;i>=1;--i)
{
for(int j=1;j<=Tf[i][0];j++)
{
k++;
H[k]=Tf[i][j];
upheap(k);
}
sol+=H[1];
H[1]=H[k];
k--;
downheap(1);
}
printf("%lld\n",sol);
}
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
citire();
initi();
solve();
return 0;
}