Cod sursa(job #615339)

Utilizator vladtarniceruVlad Tarniceru vladtarniceru Data 9 octombrie 2011 14:21:47
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

struct cmp
{
    inline bool operator()(const pair <int, int> &a, const pair <int, int> &b) const
    {
        return a.first > b.first;
    }
};
long long n, x, l, nr = 1, sol;
priority_queue <long long> Q;
pair <int, int> v[100100];
int main()
{
    ifstream f("lupu.in");
    ofstream g("lupu.out");

    f >> n >> x >> l;
    for (int i = 1; i <= n; ++i)
        f >> v[i].first >> v[i].second, v[i].first = (x - v[i].first) / l + 1;

    sort(v + 1, v + n + 1, cmp());

    for (int i = v[nr].first; i > 0; --i)
    {
        while (v[nr].first == i)
        {
            Q.push(v[nr++].second);
        }
        if (!Q.empty())
        {
            sol += Q.top();
            Q.pop();
        }
    }

    g << sol;
}