Cod sursa(job #152679)

Utilizator CezarMocanCezar Mocan CezarMocan Data 9 martie 2008 18:05:18
Problema Lupul Urias si Rau Scor 48
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct oaie{long t; long p;};

long  n,i,j,x,l,d[100100], z[10010l], h[200100],p, tmax,k;
oaie t[100100];
long long s;

bool cmp(oaie a, oaie b)
    {
    if (a.t>b.t)    
        return true;
    else
        return false;
    }
    
void adauga_heap( long x)
    {
    long poz,aux;
    p++;
    h[p]=x;
    poz=p;
    while ((h[poz]>h[poz/2])&&(poz>1))
        {
        aux=h[poz];
        h[poz]=h[poz/2];
        h[poz/2]=aux;
        poz/=2;
        }
    }
    
long long maxim( long a, long b)
    {
    if (a>b)
        return a;
       else
        return b;    
    }
    
void scoate_heap()
    {
    long poz,mx,aux;
    h[1]=h[p];
    h[p]=0;
    p--;
    poz=1;
    while ((h[poz]<h[poz*2])||(h[poz]<h[poz*2+1]))
        {
//        mx=maxim(h[poz*2],h[poz*2+1]);
        if (h[2*poz]>h[2*poz+1]) 
            {
            aux=h[poz];
            h[poz]=h[2*poz];
            h[2*poz]=aux;
            poz*=2;
            }
        else
            {
            aux=h[poz];
            h[poz]=h[2*poz+1];
            h[2*poz+1]=aux;   
            poz=poz*2+1;             
            }
            
        }
    }

int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
scanf("%ld%ld%ld",&n,&x,&l);
for (i=1;i<=n;++i)
    {
    scanf("%ld%ld",&d[i],&z[i]);
    t[i].t=(x-d[i])/l+1;
    if (d[i]>x)
        t[i].t=0;
    t[i].p=i;
    if (t[i].t>tmax)
        tmax=t[i].t;
    }
sort(t+1,t+n+1,cmp);
/*for (i=1;i<=n;i++)
    printf("%ld %ld \n",t[i].t, z[t[i].p]);*/
j=1;
s=0;
for (i=tmax;i>=1;i--)
    {
    while ((t[j].t==i))
        {
        adauga_heap(z[t[j].p]);
        j++;            
        }
/*    printf("%d\n",h[1]);
    for (k=1;k<=p;k++)
        printf("%d ",h[k]);
    printf("\n");*/
    if (p)
        {
        s+=h[1];
        scoate_heap();
        }
    }
printf("%lld\n",s);
return 0;
}