Pagini recente » Cod sursa (job #2599713) | Cod sursa (job #116936) | Cod sursa (job #1607208) | Cod sursa (job #1914301) | Cod sursa (job #313801)
Cod sursa(job #313801)
#include<stdio.h>
#include<stdlib.h>
#define N 100005
struct lupu{int t,l;}v[N];
int n,x,l,h[N],nr;
long long s;
int compar(const void*p,const void*q)
{
lupu pp=*(lupu*)p,qq=*(lupu*)q;
if (pp.t<qq.t) return 1;
if (pp.t>qq.t) return -1;
return 0;
}
void citire()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%d%d%d",&n,&x,&l);
for (int i=1; i<=n; ++i)
{
int d;
scanf("%d%d",&d,&v[i].l);
if(x==0 && d)
v[i].t=-1;
else
v[i].t=(x-d)/l;
//printf("%d ",v[i].t);
}
qsort(v+1,n,sizeof(v[0]),compar);
}
void cobor(int k)
{
int y=h[k];
while (k>1&&y>h[k/2])
{
h[k]=h[k/2];
k/=2;
}
h[k]=y;
}
void heap(int k)
{
h[++nr]=v[k].l;
cobor(nr);
}
void urc(int k)
{
int f=k;
while (true)
{
if (2*k<=nr && h[2*k]>h[f])
f=2*k;
if (2*k+1<=nr && h[2*k+1]>h[f])
f=2*k+1;
if (f==k)
return;
int aux=h[k];
h[k]=h[f];
h[f]=aux;
k=f;
}
}
void del(int k)
{
h[k]=h[nr];
--nr;
if (k>1&& h[k]>h[k/2])
cobor(k);
else
urc(k);
}
void build()
{
int j=1;
for(int i=v[1].t ; i>=0 ; --i)
{
while(j<=n && v[j].t==i)
{
heap(j);
++j;
}
if(nr)
{
s+=h[1];
del(1);
}
}
printf("%lld\n",s);
}
int main()
{
citire();
build();
return 0;
}