Cod sursa(job #3326569)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 29 noiembrie 2025 14:15:12
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;

struct Sheep {
    long long deadline; // T_i
    long long wool;     // A_i
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);

    int N;
    long long X, L;
    cin >> N >> X >> L;

    vector<Sheep> v;
    v.reserve(N);

    long long answer = 0;

    for (int i = 0; i < N; ++i) {
        long long D, A;
        cin >> D >> A;

        if (D > X) {
            // oaia nu poate fi atinsă niciodată
            continue;
        }

        if (L == 0) {
            // distanțele nu se schimbă, putem lua toate oile cu D <= X
            answer += A;
        } else {
            // calculăm deadline-ul T_i = floor((X - D) / L) + 1
            long long maxSteps = (X - D) / L + 1;
            v.push_back({maxSteps, A});
        }
    }

    if (L == 0) {
        // deja am adunat suma pentru toate oile accesibile
        cout << answer << "\n";
        return 0;
    }

    // L > 0: aplicăm greedy cu deadline și heap minim
    sort(v.begin(), v.end(), [](const Sheep& a, const Sheep& b) {
        return a.deadline < b.deadline;
    });

    priority_queue<long long, vector<long long>, greater<long long>> pq;
    long long sum = 0;

    for (auto &s : v) {
        sum += s.wool;
        pq.push(s.wool);

        // dacă avem mai multe oi alese decât ne permite deadline-ul curent
        if ((long long)pq.size() > s.deadline) {
            sum -= pq.top();
            pq.pop();
        }
    }

    answer = sum; // pentru L > 0, acesta e răspunsul

    cout << answer << "\n";
    return 0;
}