Cod sursa(job #998745)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 17 septembrie 2013 21:56:07
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define In "lupu.in"
#define Out "lupu.out"
#define PII pair< int ,int >
#define Nmax 100004
#define val second
#define time first

using namespace std;

PII v[Nmax];
vector< int >Heap;
int n;
long long sol;

inline void Read()
{
    int L, D, i, Dist;
    ifstream f(In);
    f >> n >> L >> D;
    for(i = 1;i <= n; ++i)
    {
        f >> Dist >> v[i].val;
        v[i].time = (L-Dist)/D+1;
    }
    f.close();
}

inline void Solve()
{
    sort(v+1,v+n+1);
    int i,time = v[n].time;
    for(i = n; time; --time)
    {
        while(i && v[i].time==time)
        {
            Heap.push_back(v[i].val);
            push_heap(Heap.begin(),Heap.end());
            --i;
        }
        if(!Heap.empty())
        {
            sol += Heap[0];
            pop_heap(Heap.begin(),Heap.end());
            Heap.pop_back();
        }
    }
}

inline void Write()
{
    ofstream g(Out);
    g<<sol<<"\n";
    g.close();
}

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