Cod sursa(job #3340991)

Utilizator Octa-pe-infoNechifor Octavian Octa-pe-info Data 17 februarie 2026 16:55:00
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream fin("lupu.in");
ofstream fout("lupu.out");

struct arbore{

    long long v,t;

    bool operator>(const arbore & o)const{

        if(t == o.t)
            return v < o.v;

        return t > o.t;
    }
};

int main()
{

    long long n,x,l;
    fin>>n>>x>>l;

    vector<vector<long long>>timp(n+1);
    priority_queue<arbore,vector<arbore>,greater<arbore>>pq;

    long long rez = 0;

    for(long long i=1;i<=n;i++){

        long long pz,v;
        fin>>pz>>v;

        long long aux = (max(0LL,x - pz)) / l;

        if(aux >= n)
            rez += v;
        else{

            timp[aux].push_back(v);
            pq.push({v,aux});
        }
    }

    for(long long i=0;i<=n;i++)
        sort(timp[i].begin(),timp[i].end());

    long long cnt = 0;

    priority_queue<long long,vector<long long>,greater<long long>>luat;

    while(!pq.empty()){

        auto curent = pq.top();
        pq.pop();

        if(curent.t < cnt)
            continue;

        luat.push(curent.v);

        timp[curent.t].pop_back();

        ///ma uit prin cei care expira acum
        for(long long i = timp[cnt].size() - 1;i >= 0;i--){

            if(timp[cnt][i] > luat.top()){

                luat.pop();
                luat.push(timp[cnt][i]);
            }
            else
                break;
        }

        cnt++;
    }

    while(!luat.empty()){

        rez += luat.top();
        luat.pop();
    }

    fout<<rez;

    return 0;
}