Cod sursa(job #3041136)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 30 martie 2023 23:58:47
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

const int NMAX = 100000;

struct Oaie
{
    int d;
    int a;
};

Oaie oi[1 + NMAX];

/// Greedy

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

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

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

    ios_base::sync_with_stdio(false);
    in.tie(nullptr);

    int n, x, l;
    in >> n >> x >> l;

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

    out << sol << '\n';

    in.close();
    out.close();

    return 0;
}