Cod sursa(job #3125843)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 4 mai 2023 17:41:05
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

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

const int MAX = 1e5 + 1;

int n , x , l;

struct oaie{ int p , d; };

bool cmp( oaie a , oaie b ){ return a.d > b.d;}

struct crit{

    bool operator()( int a , int b ){

        return a > b;
    }

};

oaie v[MAX];

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

signed main(){

    cin >> n >> x >> l;

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

        cin >> v[i].d >> v[i].p;
    }

    sort(v+1,v+1+n,cmp);

    int total_value = 0;

    int lupul = 0;

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

        if(lupul + v[i].d <= x){

            lupul += l;
            total_value += v[i].p;
            pq.push(v[i].p);

        }else if(!pq.empty() && lupul + v[i].d - l <= x){

            if(pq.top() >= v[i].p) continue;

            total_value -= pq.top();
            pq.pop();
            pq.push(v[i].p);
            total_value += v[i].p;
        }
    }

    cout << total_value;

    return 0;
}