Cod sursa(job #436686)

Utilizator stef2nStefan Istrate stef2n Data 8 aprilie 2010 20:07:41
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.79 kb
#include <vector>
#include <queue>
#include <algorithm>
#include <fstream>
using namespace std;

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

int N, H, U;
vector < pair <int, int> > gutui;
priority_queue <int> q;
int best = 0;


int main() {
    in >> N >> H >> U;

    gutui.resize(N);
    for (int i = 0; i < N; ++i) {
        in >> gutui[i].first >> gutui[i].second;
        if (gutui[i].first <= H)
            gutui[i].first = (H - gutui[i].first) / U;
        else
            gutui[i].first = -1;
    }
    sort(gutui.rbegin(), gutui.rend());

    for (int i = gutui[0].first, k = 0; i >= 0; --i) {
        for (; k < N && gutui[k].first == i; ++k)
            q.push(gutui[k].second);
        if (!q.empty())
            best += q.top(), q.pop();
    }

    out << best << "\n";

    return 0;
}