Cod sursa(job #3142104)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 19 iulie 2023 11:05:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
#include <queue>
#include <algorithm>

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

const long long nmax = 100005;

struct oi{
long long wool, dist;
}A[nmax];

long long n, prey, scared, sol;
priority_queue<long long> H;

bool cmp(oi x, oi y){
    if(x.dist != y.dist)
        return (x.dist < y.dist);
    else
        return (x.wool < y.wool);
}

int main()
{
    f >> n >> prey >> scared;
    for(long long i = 1; i <= n; i ++)
    {
        long long x;
        f >> x >> A[i].wool;
        A[i].dist = (prey - x) / scared;
    }
    sort(A + 1, A + n + 1, cmp);

    long long x = A[n].dist, p = n;
    while(x >= 0)
    {
        while(p && A[p].dist >= x){
            H.push(A[p].wool);
            p --;
        }

        if(!H.empty())
        {
            sol += H.top();
            H.pop();
        }

        x --;
    }

    g << sol;
    return 0;
}