Cod sursa(job #718997)

Utilizator mottyMatei-Dan Epure motty Data 21 martie 2012 12:13:48
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

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

vector < pair<int,int> > v;
multiset <long long> s;

void read() {
    int n, dMax, dTurn;
    in >> n >> dMax >> dTurn;

    v.push_back(make_pair(0, 0));

    while (n--) {
        int dist, lana;
        in >> dist >> lana;

        dist = (dMax - dist)/dTurn + 1;

        if (dist > 0)
            v.push_back(make_pair(dist, lana));
    }
}

long long solve() {
    long long res = 0;
    int index = v.size() - 1;
    s.insert(-v[index].second);
    index--;

    while (index >= 0) {
        while (index >= 0 && v[index].first == v[index + 1].first) {
            s.insert(-v[index].second);
            --index;
        }

        int toTake = v[index + 1].first - v[index].first;
        while (toTake-- && !s.empty()) {
            res -= *s.begin();
            s.erase(s.begin());
        }

        s.insert(-v[index].second);
        --index;
    }

    return res;
}

int main() {
    read();
    sort(v.begin(), v.end());

    out << solve() << "\n";

    return 0;
}