Cod sursa(job #2884306)

Utilizator acostin643costin andrei acostin643 Data 2 aprilie 2022 20:38:55
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 100000;

int N;
long long X, L, k, in, zmax, inz = 1, S, h[NMAX + 5];
//in este numarul de noduri din heap

struct oi
{
    int zile, lana;
} oaie[NMAX + 5];

bool ok(oi a, oi b)
{
    if(a.zile == b.zile)
        return a.lana > b.lana;
    return a.zile > b.zile;
}

int father(int nod)
{
    return nod / 2;
}

int left_son(int nod)
{
    return nod * 2;
}

int right_son(int nod)
{
    return nod * 2 + 1;
}

void percolate(int nod)
{
    while(nod > 1 && h[nod] > h[father(nod)])
    {
        swap(h[nod], h[father(nod)]);
        nod = father(nod);
    }
}

void sift(int nod)
{
    int son = 0;
    do
    {
        son = 0;
        if(left_son(nod) <= in)
        {
            son = left_son(nod);
            if(right_son(nod) <= in && h[right_son(nod)] > h[son])
                son = right_son(nod);
            if(h[son] <= h[nod])
                son = 0;
            if(son)
            {
                swap(h[son], h[nod]);
                nod = son;
            }
        }
    }while(son);
}

void insrt(int val)
{
    h[++in] = val;
    percolate(in);
}

void cut(int key)
{
    h[key] = h[in];
    in--;
    sift(key);
}

int main()
{
    int x, y;
    fin >> N >> X >> L;
    for(int i = 1; i <= N; i++)
    {
        fin >> x >> y;
        if(x <= X)
        {
            oaie[++k].zile = (X - x) / L + 1;
            if(oaie[k].zile > zmax)
                zmax = oaie[k].zile;
            oaie[k].lana = y;
        }
    }

    sort(oaie + 1, oaie + k + 1, ok);

    for(int i = zmax; i >= 1; i--)
    {
        bool ok = 0;
        while(oaie[inz].zile == i)
        {
            insrt(oaie[inz].lana);
            inz++, ok = 1;
        }
        if(in)
        {
            S += h[1];
            cut(1);
        }
    }

    fout << S;

    fin.close();
    fout.close();
    return 0;
}