Cod sursa(job #1770191)

Utilizator ancabdBadiu Anca ancabd Data 3 octombrie 2016 21:06:09
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <queue>
#include <algorithm>

#define NMAX 200007
#define DIM 100007

using namespace std;

ifstream fin ("lupu.in");
ofstream fout ("lupu.out");

int n, x, l, poz = 1, first, pos;
long long sum;
priority_queue <int> s;

struct oaie
{
    int dist;
    int w;
} v[NMAX];

bool cmp(const oaie &a, const oaie &b)
{
    return a.dist < b.dist;
}

inline void add(const int &edge)
{
    while(v[poz].dist <= edge && poz <= n)
    {
        s.push(v[poz].w);
        ++poz;
    }
}

int main()
{
    fin >> n >> x >> l;
    for(int i = 1; i <= n; ++i)
        fin >> v[i].dist >> v[i].w;

    sort(v + 1, v + n + 1, cmp);
    for(int lim = 0; lim <= x; lim += l)
    {
        add(lim);
        if(s.empty()) continue;
        first = s.top();
        s.pop();
        sum += first;
    }
    fout << sum;
    return 0;
}