Cod sursa(job #1052566)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 11 decembrie 2013 15:40:00
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <algorithm>
#define Nmax 100005

using namespace std;

int N,X,L,H[Nmax];

struct pereche
{
    int timp,lana;
    bool operator <(const pereche &A) const
    {
        return timp<A.timp;
    }
};
pereche t[Nmax];

inline void Swap(int i, int j)
{
    int aux;
    aux=H[i]; H[i]=H[j]; H[j]=aux;
}

inline void UpHeap(int k)
{
    int tata;
    tata=k/2;
    while(k>1 && H[k]>H[tata])
    {
        Swap(k,tata);
        k=tata; tata=k/2;
    }
}

inline void DownHeap(int k)
{
    int fiu,gata;
    fiu=2*k; gata=0;
    while(k<=H[0]/2 && !gata)
    {
        if(fiu+1<=H[0] && H[fiu+1]>H[fiu])
            ++fiu;
        if(H[k]>=H[fiu])
            gata=1;
        else
        {
            Swap(k,fiu);
            k=fiu; fiu=2*k;
        }
    }
}

inline void Read()
{
    int i,dist,lana,len,timp;
    ifstream fin("lupu.in");
    fin>>len>>X>>L;
    for(i=1;i<=len;++i)
    {
        fin>>dist>>lana;
        timp=(X-dist)/L+1;
        ++N;
        t[N].timp=timp; t[N].lana=lana;
    }
    fin.close();
}

inline void Solve()
{
    int i,timp;
    long long sol=0;
    sort(t+1,t+N+1);
    i=N;
    while(i>0)
    {
        timp=t[i].timp;
        while(t[i].timp==timp)
        {
            H[++H[0]]=t[i].lana;
            UpHeap(H[0]);
            --i;
        }
        if(H[0])
        {
            sol+=H[1];
            H[1]=H[H[0]--];
            DownHeap(1);
        }
    }
    ofstream fout("lupu.out");
    fout<<sol<<"\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}