Cod sursa(job #1528884)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 20 noiembrie 2015 10:41:57
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <algorithm>
#define right(x) ((x<<1)+1)
#define left(x) (x<<1)
#define dad(x) (x>>1)

using namespace std;

long long ans=0LL;
int nr=0,i,x,n,l,last,j,heap[100007];
pair<int,int> a[100007];

inline void POP(int x)
{
    if(right(x)<=nr)
    {
         if(heap[left(x)]>=heap[right(x)] && heap[left(x)]>heap[x])
         {
            swap(heap[x],heap[left(x)]);
            POP(left(x));
         }
         else
         if(heap[left(x)]<heap[right(x)] && heap[right(x)]>heap[x])
         {
            swap(heap[x],heap[right(x)]);
            POP(right(x));
         }
    }
    else if(left(x)<=nr)
    {
         if(heap[left(x)]>heap[x])
         {
            swap(heap[x],heap[left(x)]);
            POP(left(x));
         }
    }
}

inline void INSERT(int p)
{
    if(p==1) return;

    if(heap[p]>heap[dad(p)])
    {
        swap(heap[p], heap[dad(p)]);
        INSERT(dad(p));
    }
}

int main()
{
    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",&a[i].first,&a[i].second);
       if(!l) {if(a[i].first<=x) ans+=a[i].second;}
       else a[i].first=(x-a[i].first)/l;
    }
    if(!l)
    {
        printf("%lld\n",ans);
        return 0;
    }
    sort(a+1,a+n+1);

    i=n;
    for(x=a[n].first;x>=0;--x)
    {
         while(i && a[i].first==x)
         {
             heap[++nr]=a[i].second;
             INSERT(nr);
             --i;
         }

         if(nr)
         {
             ans+=1LL*heap[1];
             heap[1]=heap[nr];
             --nr;
             POP(1);
         }

    }

    printf("%lld\n",ans);

    return 0;
}