Cod sursa(job #152625)

Utilizator CezarMocanCezar Mocan CezarMocan Data 9 martie 2008 16:50:59
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 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,s;
oaie t[100100];

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];
    p--;
    poz=1;
    while ((h[poz]<maxim(h[poz*2],h[poz*2+1])))
        {
        mx=maxim(h[poz*2],h[poz*2+1]);
        if (mx==h[2*poz]) 
            {
            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;
    if (d[i]>x)
        t[i].t=-1;
    t[i].p=i;
    }
sort(t+1,t+n+1,cmp);
/*for (i=1;i<=n;i++)
    printf("%ld %ld \n",t[i].t, t[i].p);*/
i=1;
while (i<=n)
    {
    j=i;
    while ((t[j].t==t[i].t)&&(j<=n))
        {
        if (t[j].t>=0)
            adauga_heap(z[t[j].p]);
        ++j;            
        }
    if (t[j-1].t>=0)
        {
        s+=h[1];
        scoate_heap();
        }
    i=j;  
    }
printf("%ld\n",s);
return 0;
}