Pagini recente » Cod sursa (job #2331868) | Cod sursa (job #2207790) | Cod sursa (job #1033978) | Cod sursa (job #2827930) | Cod sursa (job #346792)
Cod sursa(job #346792)
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 100001
struct lupu{int l,d;}v[N];
int n,nr,x,l,h[N];
bool compar(const lupu&a,const lupu&b)
{
if (a.d>b.d)
return true;
if (a.d==b.d&&a.l>b.l)
return true;
return false;
}
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)
{
scanf("%d%d",&v[i].d, &v[i].l);
v[i].d=(x-v[i].d)/l;
}
sort (v+1,v+1+n,compar);
}
void urc(int k)
{
int key=h[k];
while (k-1&&key>h[k/2])
{
h[k]=h[k/2];
k/=2;
}
h[k]=key;
}
void add(int k)
{
h[++nr]=v[k].l;
urc(nr);
}
void cobor(int k)
{
int f=k;
while (true)
{
if (2*k<=nr&&h[f]<h[2*k])
f=2*k;
if (2*k+1<=nr&&h[f]<h[2*k+1])
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])
urc(k);
else
cobor(k);
}
void build()
{
int j=1,lana=0;
for (int i=v[1].d;i>=0; --i)
{
while (j<=n&&v[j].d==i)
{
add(j);
++j;
}
if (nr)
{
lana+=h[1];
del(1);
}
}
printf("%d",lana);
}
int main()
{
citire();
build();
return 0;
}