Cod sursa(job #763214)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 1 iulie 2012 14:20:40
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define x first
#define y second

vector <pair <int, int> > v;
priority_queue <int> heap;
int n, X, l, a, b, sol, p;

int cmp(pair <int, int> a, pair <int, int> b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x > b.x;
}

int main()
{
    int i;
    freopen ("lupu.in", "r", stdin);
    freopen ("lupu.out", "w", stdout);
    scanf("%d %d %d", &n, &X, &l);
    for(i = 1; i <= n; ++i) {
        scanf("%d %d", &a, &b);
        v.push_back(make_pair(a, b));
    }
    sort(v.begin(), v.end(), cmp);
    for(i = 0; i < v.size(); ++i) {
        if(v[i].x + p * l <= X) {
            sol += v[i].y;
            heap.push(-v[i].y);
            ++p;
            continue;
        }
        if(!heap.empty() && -v[i].y < heap.top()) {
            sol += heap.top();
            sol += v[i].y;
            heap.pop();
            heap.push(-v[i].y);
        }
    }
    printf("%d", sol);


    return 0;
}