Pagini recente » Cod sursa (job #1506053) | Statistici Sebastian Georgescu Andrei (Sebi_geo) | Cod sursa (job #1292480) | Cod sursa (job #1467856) | Cod sursa (job #331540)
Cod sursa(job #331540)
#include <stdio.h>
#define DIM 100005
struct nod {int x;
nod *urm;} *lst[DIM];
int h[DIM],d[DIM],a[DIM];
int n,x,l,m,nrt,tmax;
void add (int a,int b)
{
nod *p=new nod;
p->x=b;
p->urm=lst[a];
lst[a]=p;
}
void read ()
{
int i,nr;
scanf ("%d%d%d",&n,&x,&l);
for (i=1; i<=n; ++i)
{
scanf ("%d%d",&nr,&a[i]);
if (nr<=x)
d[i]=(x-nr)/l+1;
if (d[i])
add (d[i],a[i]);
if (d[i]>tmax)
tmax=d[i];
}
}
void swap (int &a,int &b)
{
int aux=a;
a=b;
b=aux;
}
void upheap (int nod)
{
for (; nod>1 && h[nod]>h[nod/2]; nod/=2)
swap (h[nod],h[nod/2]);
}
void downheap (int nod)
{
int son;
do
{
son=0;
if (2*nod<=m)
{
son=2*nod;
if (2*nod+1<=m && h[2*nod+1]>h[2*nod])
son=2*nod+1;
if (h[son]<=h[nod])
son=0;
}
if (son)
{
swap (h[nod],h[son]);
nod=son;
}
}
while (son);
}
void solve ()
{
nod *p;
int i;
for (i=tmax; i>=1; --i)
{
for (p=lst[i]; p; p=p->urm)
{
h[++m]=p->x;
upheap (m);
}
if (m)
{
nrt+=h[1];
h[1]=h[m--];
downheap (1);
}
}
printf ("%d",nrt);
}
int main ()
{
freopen ("lupu.in","r",stdin);
freopen ("lupu.out","w",stdout);
read ();
solve ();
return 0;
}