Cod sursa(job #883248)

Utilizator AndreyPAndrei Poenaru AndreyP Data 19 februarie 2013 21:07:13
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.05 kb
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fs first
#define sc second

#define N_MAX 100010

int N, H, U;
priority_queue<int> q;
pii vg[N_MAX];

int main() {
    ll res = 0LL;

    freopen("gutui.in", "r", stdin);
    freopen("gutui.out", "w", stdout);

    scanf("%d%d%d", &N, &H, &U);

    for (int i = 0; i < N; ++i) {
        scanf("%d%d", &vg[i].fs, &vg[i].sc);

        if (vg[i].fs > H) {
            --i;
            --N;
        }

        vg[i].fs = (H - vg[i].fs) / U;
    }

    if (N == 0) {
        fputs("0\n", stdout);
        return 0;
    }

    sort(vg, vg + N, greater< pii >());

    for (int i = vg[0].fs, j = 0; i >= 0; --i) {
        for (; j < N && vg[j].fs == i; ++j) {
            q.push(vg[j].sc);
        }

        if (q.empty()) {
            if (j == N) {
                break;
            }

            i = vg[j].fs + 1;
            continue;
        }

        res += (ll)q.top();
        q.pop();
    }

    printf("%lld\n", res);

    return 0;
}