Cod sursa(job #631349)

Utilizator Teodor94Teodor Plop Teodor94 Data 7 noiembrie 2011 21:02:42
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 100002;

struct lupu {
    int d, g;
};

int n, x, l;
lupu v[N];
priority_queue<int> heap;

bool comp(lupu a, lupu b) {
    return a.d < b.d;
}

void citire() {
    scanf("%d%d%d", &n, &x, &l);
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &v[i].d, &v[i].g);
}

void rez() {
    int gmax = 0, distmax = x;

    while (distmax - l >= v[1].d)
        distmax -= l;

    int i = 1;

    while (1) {
        if (v[i].d > distmax || i >n) {
            if (!heap.empty()) {
                gmax += heap.top();
                heap.pop();
            }

            distmax += l;

            if (distmax > x)
                break;
        }

        if (v[i].d <= distmax && i <= n) {
            heap.push(v[i].g);
            ++i;
        }
    }

    printf("%d\n", gmax);
}

int main() {
    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);

    citire();

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

    rez();

    return 0;
}