Cod sursa(job #2839434)

Utilizator octavian2411Cretu Octavian octavian2411 Data 25 ianuarie 2022 21:53:22
Problema Lupul Urias si Rau Scor 84
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb

#include <fstream>
#include <algorithm>

using namespace std;

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

const int N= 1e5+1;

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

int n, x, l, l1;
/*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 true;
    }
    if (x.dist==y.dist)
    {
        if (x.lana<y.lana)
            return true;
    }
    return false;
}

void urca(int p)
{
    while (p > 1 && heap[p] > heap[p/2])
    {
        swap(heap[p], heap[p/2]);
        p /= 2;
    }
}

void adauga(int x)
{
    heap[++l1]=x;
    urca(l1);
}

void coboara(int p)
{
    int fs = 2*p, fd = 2*p + 1, bun = p;
    if (fs <= l1 && heap[fs] > heap[bun])
    {
        bun = fs;
    }
    if (fd <= l1 && heap[fd] > heap[bun])
    {
        bun = fd;
    }
    if (bun != p)
    {
        swap(heap[p], heap[bun]);
        coboara(bun);
    }
}

void stergere()
{
    heap[1]=heap[l1];
    l1--;
    coboara(1);
}

int main()
{
    in>>n>>x>>l;
    for (int i=1;i<=n;i++)
    {
        int aux1, aux2;
        in>>aux1>>aux2;
        if (x-aux1>=0)
        {
            oi[i].dist=(x-aux1)/l;
            oi[i].lana=aux2;
        }
        else
            n--;
    }
    sort(oi+1,oi+n+1,CompMic);
    int nrmax=oi[n].dist, k=n;
    while(nrmax>=0)
    {
        while (k && oi[k].dist>=nrmax)
        {
            adauga(oi[k].lana);
            k--;
        }
        if (heap[1])
        {
            s+=heap[1];
            stergere();
        }
        nrmax--;

    }
    out<<s;
    return 0;
}