Cod sursa(job #2839178)

Utilizator db_123Balaban David db_123 Data 25 ianuarie 2022 13:36:48
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

const int DIM = 100005;

ifstream cin("lupu.in");
ofstream cout("lupu.out");

struct Oaie
{
    long long timp;
    long long lana;
};

long long n, dist, step, i, d, timpRamas, sol;

vector<Oaie> v;

priority_queue<long long> wool;

bool comp(Oaie o1, Oaie o2)
{
    if (o1.timp < o2.timp)
        return true;
    return false;
}

int main()
{
    Oaie oaie;
    cin >> n >> dist >> step;
    for (i = 1; i <= n; i++) {
        cin >> d;
        cin >> oaie.lana;
        if (d <= dist) {
            if (step == 0)
                oaie.timp = DIM;
            else {
                oaie.timp = (dist - d) / step;
                if (oaie.timp > DIM)
                    oaie.timp = DIM;
            }
        }
        else
            oaie.timp = -1;
        v.push_back(oaie);
    }
    sort(v.begin(), v.end(), comp);

    timpRamas = v[v.size()-1].timp;

    i = v.size()-1;
    while (timpRamas >= 0) {
        while (i >= 1 && v[i].timp == timpRamas) {
            wool.push(v[i].lana);
            i--;
        }
        if (!wool.empty()) {
            sol += wool.top();
            wool.pop();
        }
        timpRamas--;
    }
    cout << sol;
    cin.close();
    cout.close();
    return 0;
}