Cod sursa(job #3197112)

Utilizator iusty64Iustin Epanu iusty64 Data 25 ianuarie 2024 17:51:04
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 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++){
        int dist, val;
        fin>>dist>>val;
        oi[i].distOaie = (distLup - dist) / adaos;
        oi[i].valOaie = val;
    }
    sort(oi + 1, oi + n + 1, [](const oaie &a, const oaie &b){
        return a.distOaie < b.distOaie;
    });
    long long el = oi[n].distOaie, cnt = n;
    while(el>=0){
        while(cnt && el<=oi[cnt].distOaie){
            Q.push(oi[cnt].valOaie);
            cnt--;
        }
        if(!Q.empty()){
            suma += Q.top();
            Q.pop();
        }
        el--;
    }
    fout<<suma;
    return 0;
}