Cod sursa(job #1782445)

Utilizator dnprxDan Pracsiu dnprx Data 18 octombrie 2016 09:42:10
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <bits/stdc++.h>
#define nmax 100005

using namespace std;

long long n, da, cr, sol;

struct Pereche
{
    long long dist, cost;
};
Pereche v[nmax];

bool Comp(const Pereche a, const Pereche b)
{
    return a.dist > b.dist || (a.dist == b.dist && a.cost > b.cost);
}

priority_queue <long long> heap;

int main()
{
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    fin >> n >> da >> cr;

    for(int i = 1; i <= n; ++i)
        fin >> 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();
    }

    fout << sol << "\n";
    fout.close();
    return 0;
}