Cod sursa(job #3196883)

Utilizator iusty64Iustin Epanu iusty64 Data 24 ianuarie 2024 21:58:36
Problema Lupul Urias si Rau Scor 12
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

const int Vmax = 100001;

struct oaie{
    long long distOaie;
    long long valOaie;
}oi[Vmax];

long long n, distLup, adaos;
long long suma;

priority_queue<long long> Q;

int main(){
    ifstream fin("lupu.in");
    ofstream fout("lupu.out");
    fin>>n>>distLup>>adaos;
    for(long long i=1;i<=n;i++){
        fin>>oi[i].distOaie;
        fin>>oi[i].valOaie;
    }
    sort(oi + 1, oi + n + 1, [](const oaie &a, const oaie &b){
        return a.valOaie > b.valOaie;
    });
    long long contorDistanta = 0;
    for(long long i=1;i<=n;i++){
        bool ok = 1;
        oi[i].distOaie += contorDistanta;
        while(!Q.empty() && oi[i].distOaie > distLup){
            if(-Q.top() + contorDistanta <= distLup){
                long long nouTop = -Q.top() + contorDistanta;
                Q.pop();
                Q.push(-nouTop);
                oi[i].distOaie -= contorDistanta;
            }
            else{
                ok=0;
                break;
            }
        }
        if(!ok)
            continue;
        Q.push(-oi[i].distOaie);
        suma+=oi[i].valOaie;
        contorDistanta+=adaos;
    }
    fout<<suma;
    return 0;
}