Cod sursa(job #599879)

Utilizator elfusFlorin Chirica elfus Data 29 iunie 2011 20:49:59
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include<stdio.h>
#define LMAX 100100
#include<algorithm>
struct pozdy
{
    int x,cst;
} x[LMAX];

int H[LMAX];

using namespace std;

inline bool comp(pozdy A,pozdy B)
{
    return A.x < B.x;
}

void baga(int val)
{
   int nod,aux;
   H[++H[0]]=val; nod=H[0];
   while(nod>>1 > 0 && H[nod]>H[nod>>1])
        {
            aux=H[nod];
            H[nod]=H[nod>>1];
            H[nod>>1]=aux;
            nod=nod>>1;
        }
}

void scoate()
{
    int nod=1,fiu,aux;
    H[1]=H[H[0]--];
    if(!H[0])
        return;
    do
    {
        fiu=0;
        if(nod<<1 <= H[0])
            fiu=nod<<1;
        if(nod<<1 < H[0] && H[fiu]<H[(nod<<1)+1])
            fiu=(nod<<1)+1;
        if(H[nod]>=H[fiu])
            fiu=0;
        else
        {
            aux=H[nod];
            H[nod]=H[fiu];
            H[fiu]=aux;
            nod=fiu;
        }
    }
    while(fiu);

}

int main()
{
    int n,X,L,i,j;

    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);

    scanf("%d%d%d",&n,&X,&L);
    for(i=1;i<=n;i++)
        {
            scanf("%d%d",&x[i].x,&x[i].cst);
            x[i].x=(X-x[i].x)/L+1;
            if(x[i].x<0)
                i--,n--;
        }
    sort(x+1,x+n+1,comp);
    long long s=0;
    for(i=n;i>=1;i--)
        {
            baga(x[i].cst);
            if(x[i].x!=x[i-1].x)
                for(j=1;j<=x[i].x-x[i-1].x && H[0];j++)
                    {
                        s+=H[1];
                        scoate();
                    }
        }
    printf("%lld",s);
    return 0;
}