Cod sursa(job #491165)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 octombrie 2010 12:19:29
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <fstream>
#include <algorithm>

using namespace std;

const char InFile[]="lupu.in";
const char OutFile[]="lupu.out";
const int MaxN=100010;

struct oaie
{
    oaie(int lana2=0, int pos2=0):lana(lana2),pos(pos2){}
    int lana,pos;
};

ifstream fin(InFile);
ofstream fout(OutFile);

int H[MaxN],HSize,n,x,l,d,a;
long long lana;
oaie V[MaxN];

bool cmp_oaie(oaie a, oaie b)
{
    return a.pos>b.pos;
}

inline int parent(int nod)
{
    return nod>>1;
}

inline int left(int nod)
{
    return nod<<1;
}

inline int right(int nod)
{
    return (nod<<1)+1;
}

void heap_up(int nod)
{
    int p=parent(nod);
    while(p>0 && H[p]<H[nod])
    {
        int aux=H[p];
        H[p]=H[nod];
        H[nod]=aux;
        nod=p;
        p=parent(nod);
    }
}

void heap_down(int nod)
{
    while(true)
    {
        int ind=nod;
        int l=left(nod);
        if(l<=HSize)
        {
            if(H[l]>H[ind])
            {
                ind=l;
            }
        }
        int r=right(nod);
        if(r<=HSize)
        {
            if(H[r]>H[ind])
            {
                ind=r;
            }
        }
        if(ind!=nod)
        {
            int aux=H[nod];
            H[nod]=H[ind];
            H[ind]=aux;
            nod=ind;
        }
        else
        {
            break;
        }
    }
}

int main()
{
    fin>>n>>x>>l;
    for(register int i=0;i<n;++i)
    {
        fin>>d>>a;
        V[i].lana=a;
        V[i].pos=(x-d)/l+1;
    }
    fin.close();

    sort(V,V+n,cmp_oaie);

    int ind=0;
    for(register int i=V[0].pos;i>0;--i)
    {
        while(V[ind].pos==i)
        {
            H[++HSize]=V[ind++].lana;
            heap_up(HSize);
        }
        if(HSize>0)
        {
            lana+=(long long)H[1];
            H[1]=H[HSize--];
            heap_down(1);
        }
    }

    fout<<lana;
    fout.close();
    return 0;
}