Cod sursa(job #334683)

Utilizator DraStiKDragos Oprica DraStiK Data 27 iulie 2009 17:19:16
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#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,tmax;
long long nrt;

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 ("%lld",nrt);
}

int main ()
{
    freopen ("lupu.in","r",stdin);
    freopen ("lupu.out","w",stdout);
    read ();
    solve ();
    return 0;
}