Cod sursa(job #1525489)

Utilizator cristina_borzaCristina Borza cristina_borza Data 15 noiembrie 2015 09:47:22
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <queue>
#include <fstream>
#include <algorithm>

#define NMAX 100005

using namespace std;

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

int n , da , cr , sol;

struct bla {int dist , cost;} v[NMAX];

bool comp(bla a , bla b) {
    return a.dist > b.dist || (a.dist == b.dist && a.cost > b.cost);
}

priority_queue <int> heap;

int main() {
    f >> n >> da >> cr;

    for(int i = 1 ; i <= n ; ++i) {
        f >> v[i].dist >> v[i].cost;
    }

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

    for(int i = 1 ; i <= n ; ++i) {
        if(v[i].dist <= da) {
            heap.push(-v[i].cost);
            da -= cr;
        }

        else {
            if(!heap.empty()) {
                if(-heap.top() < v[i].cost) {
                    heap.pop();
                    heap.push(-v[i].cost);
                }
            }
        }
    }

    while(!heap.empty()) {
        sol -= heap.top();
        heap.pop();
    }

    g << sol;
    return 0;
}