Cod sursa(job #3125303)

Utilizator RalucaioneteRalucaIonete Ralucaionete Data 2 mai 2023 17:06:51
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;

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

const int N=1e5;

struct oi
{
    int d;
    int a;
};

oi oaie[N+1];
long long sol;
int ratie;
priority_queue<int, vector<int>, greater<int>> pq;

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

int main()
{
    int n, x, l;
    cin >> n >> x >> l;
    for(int i=1; i<=n; i++)
        cin >> oaie[i].d >> oaie[i].a;

    sort(oaie+1, oaie+1+n, comp); ///sortam oile dupa distanta fata de lup

    for(int i=n; i>=1; i--)
    {
        if(oaie[i].d + ratie <=x) ///prindem intai oile cele mai departate (ele se vor departa mai curand cu l)
        {
            sol+=oaie[i].a;
            ratie+=l;
            pq.emplace(oaie[i].a);
        }
        else if(!pq.empty() && oaie[i].d + ratie - l <= x && oaie[i].a > pq.top())
        {
            ///daca nu mai avem oi disponibile cautam o oaie mai putin departata cu mai multa lana
            sol-=pq.top();
            pq.pop();
            pq.emplace(oaie[i].a);
            sol+=oaie[i].a;
        }
    }
    cout << sol;
    return 0;

}