Cod sursa(job #3041126)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 30 martie 2023 23:34:54
Problema Lupul Urias si Rau Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <queue>

using namespace std;

struct Oaie
{
    int a;
    int tMax;

    Oaie() = default;

    Oaie(int a, int tMax) : a(a), tMax(tMax) {};

    bool operator > (const Oaie& other) const
    {
        if (this->tMax == other.tMax)
            return this->a < other.a;
        return this->tMax > other.tMax;
    }
};

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

/// Greedy
/// Ideea e ca vrem ca oile ce nu mai pot fi prinse dupa timpul T sa le prindem cat mai aproape de acel timp final, ca sa permitem intre timp sa prindem alte oi ce scapa mai repede.

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++)
    {
        int d, a;
        in >> d >> a;

        int tMax;
        if (d > x)
            tMax = 0;
        else if (d == x)
            tMax = 1;
        else
            tMax = 1 + (x - d) / l;

        pq.emplace(a, tMax);
    }

    int tCrt = 1;

    long long sol = 0;

    while (!pq.empty())
    {
        if (tCrt <= pq.top().tMax)
        {
            sol += pq.top().a;
            pq.pop();
            tCrt++;
        }
        else
            pq.pop();
    }

    out << sol << '\n';

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

    return 0;
}