Cod sursa(job #2839447)

Utilizator octavian2411Cretu Octavian octavian2411 Data 25 ianuarie 2022 22:41:15
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <queue>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N= 1e5+10;

priority_queue <int> heap;


struct oaie
{
    long long dist, lana;
}oi[N];

long long s, n, x, l;
/*void afisare()
{
    for (int i=1;i<=l1;i++)
    {
        out<<heap[i]<<" ";
    }
    out<<endl;
}*/
bool CompMic(oaie x, oaie y)
{
    if (x.dist==y.dist)
    {
        return x.lana>y.lana;
    }
    return x.dist<y.dist;
}

int main()
{
    in>>n>>x>>l;
    for (long long i=1;i<=n;i++)
    {
        long long aux;
        in>>aux>>oi[i].lana;
        if (l!=0 && x-aux>=0)
            oi[i].dist=(x-aux)/l;
        else
        {
            if (l==0)
                oi[i].dist=N;
            else
            {
               oi[i].dist=-1;
            }
        }
    }
    sort(oi+1,oi+n+1,CompMic);
    long long nrmax=oi[n].dist, k=n;
    while(nrmax>=0)
    {
        while (k>=1 && oi[k].dist==nrmax)
        {
            heap.push(oi[k].lana);
            k--;
        }
        if (!heap.empty())
        {
            s+=heap.top();
            heap.pop();
        }
        nrmax--;

    }
    out<<s;
    return 0;
}