Cod sursa(job #2032791)

Utilizator osiaccrCristian Osiac osiaccr Data 5 octombrie 2017 18:08:12
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <fstream>
#include <queue>
#include <algorithm>
#define DEF 100001
#define INF 9223372036854775807

using namespace std;

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

struct oaie {
    int l;
    long long d;
} v[DEF];

priority_queue < int, vector <int> > S;

int n, x, L, _i;

long long sol, Tmax;

bool cmp (const oaie &a, const oaie &b) {
    return a.d > b.d;
}

int main () {
    fin >> n >> x >> L;
    for (int i = 1; i <= n; i++) {
        fin >> v[i].d >> v[i].l;
        if (v[i].d > x) {
            v[i].d = INF;
            continue;
        }
        v[i].d = (x - v[i].d) / L + 1;
        if (v[i].d < 0) {
            v[i].d = INF;
            continue;
        }
        if (v[i].d > Tmax)
            Tmax = v[i].d;

    }

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

    _i = 1;
    while (v[_i].d != Tmax)
        _i++;
    for (long long i = Tmax; i >= 1; i--) {
        while (v[_i].d == i) {
            S.push (v[_i].l);
            _i++;
        }
        sol += S.top ();
        S.pop ();
    }

    fout << sol;

    return 0;
}