Cod sursa(job #727995)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 28 martie 2012 13:50:44
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb

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

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

int main ()
{
    std::ifstream input("lupu.in");
    int n,distanta_max,distanta;
    input >> n >> distanta_max >> distanta;
    std::pair<int, 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,limit);
    --ptr;
    int moment(ptr->first);
    long long rez(0);
    std::priority_queue<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;
}