Cod sursa(job #330544)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 10 iulie 2009 14:32:33
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<stdlib.h>
#define Nmx 100001
#define Mare 100000001

int L[Nmx],n,X,l;
int H[Nmx],k,T[Nmx],Tmx;
int *Tf[Mare];

void citire()
{
    scanf("%d%d%d",&n,&X,&l);
    int x;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&x,&L[i]);
        if(X>=x)
          {
              T[i]=(X-x)/l+1;
              if(T[i]>Tmx)
                Tmx=T[i];
          }
    }
}

void initi()
{
    for(int i=1;i<=Tmx;++i)
    {
        Tf[i]=(int *)realloc(Tf[i],sizeof(int));
        Tf[i][0]=0;
    }
    for(int i=1;i<=n;++i)
    {
        if(T[i]!=0)
        {
            int j=i;
            i=T[i];
            Tf[i][0]++;
            Tf[i]=(int *)realloc(Tf[i],(Tf[i][0]+1)*sizeof(int));
            Tf[i][Tf[i][0]]=L[j];
            i=j;
        }
    }
}

void upheap(int k)
{
    while(k>1)
    {
        if(H[k]>H[k/2])
        {
            int t=H[k];
            H[k]=H[k/2];
            H[k/2]=t;
            k=k/2;
        }
        else return;
    }
}

void downheap(int K)
{
    int t;
    while(K<=k)
    {
        if(K*2<=k)
        {
            t=K*2;
            if(K*2+1<=k)
              if(H[t+1]>H[t])
                ++t;
        }
        else return;
        if(H[K]<H[t])
        {
            int x=H[K];
            H[K]=H[t];
            H[t]=x;
            K=t;
        }
        else return ;
    }
}

void solve()
{
    long long sol=0;
    for(int i=Tmx;i>=1;--i)
    {
        for(int j=1;j<=Tf[i][0];j++)
          {
            k++;
            H[k]=Tf[i][j];
            upheap(k);
          }
        sol+=H[1];
        H[1]=H[k];
        k--;
        downheap(1);
    }
    printf("%lld\n",sol);
}


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