Cod sursa(job #727950)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 28 martie 2012 13:15:20
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb

#include <fstream>
#include <queue>
#include <algorithm>

std::pair<unsigned int, unsigned int> oi [100000];

int main ()
{
    std::ifstream input("lupu.in");
    unsigned int n,distanta_max,distanta;
    input >> n >> distanta_max >> distanta;
    std::pair<unsigned int, unsigned int> *ptr(oi),*limit(oi + n);
    do
    {
        input >> ptr->first >> ptr->second;
        ptr->first = (distanta_max - ptr->first) / distanta + 1;
        ++ptr; 
    }
    while (ptr < limit);
    input.close();
    std::sort(oi,oi + n);
    --ptr;
    unsigned int moment(ptr->first);
    long long rez(0);
    std::priority_queue<unsigned int> coada;
    do
    {
        while (ptr >= oi && ptr->first == moment)
        {
            coada.push(ptr->second);
            --ptr;
        }
        if (!coada.empty())
        {
            rez += coada.top();
            coada.pop();
        }
        --moment;
    }
    while (moment);
    std::ofstream output("lupu.out");
    output << rez << '\n';
    output.close();
    return 0;
}