Cod sursa(job #3120915)

Utilizator unomMirel Costel unom Data 9 aprilie 2023 12:52:25
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

struct Oaie
{
    int d;
    int a;
};

Oaie oi[100005];


bool comp(const Oaie& a, const Oaie& b)
{
    return a.d < b.d;
}

priority_queue<int, vector<int>, greater<int>> pq;

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


    int n, x, l;
    f >> n >> x >> l;

    for (int i = 1; i <= n; i++)
    {
        f >> oi[i].d >> oi[i].a;
    }

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

    long long sol = 0;

    int ratie = 0;

    for (int i = n; i >= 1; i--)
    {
        if (oi[i].d + ratie <= x)
        {
            sol += oi[i].a;
            ratie += l;
            pq.emplace(oi[i].a);
        }
        else if (!pq.empty() && oi[i].d + ratie - l <= x && oi[i].a > pq.top())
        {
            sol -= pq.top();
            pq.pop();
            pq.emplace(oi[i].a);
            sol += oi[i].a;
        }
    }

    g << sol << '\n';


    return 0;
}