Cod sursa(job #2788081)

Utilizator Stefan_DomuncoStefan Domunco Stefan_Domunco Data 24 octombrie 2021 21:19:53
Problema Lupul Urias si Rau Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5+5;
struct oaie
{
    int mutari, lana;
}w[NMAX];
//max_heap
int h[NMAX], nrel;
long long sum = 0;

int root()
{
    return h[1];
}

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

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

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

///in jos
void sift(int poz)
{
    int max_son;
    do
    {
        max_son = 0;
        if(left_son(poz) <= nrel)
        {
            max_son = left_son(poz);
            if(right_son(poz) <= nrel && h[max_son] < h[right_son(poz)])
                max_son = right_son(poz);
        }

        if(max_son == 0)
            break ;
        if(h[max_son] < h[poz])
            max_son = 0;
        else swap(h[max_son], h[poz]), poz = max_son;
    }while(max_son != 0);
}


///in sus
void percolate(int poz)
{
    while(poz > 1 && h[father(poz)] < h[poz]) swap(h[father(poz)], h[poz]), poz = father(poz);
}

void add(int val)
{
    h[++nrel] = val;
    percolate(nrel);
}

bool comp(oaie a, oaie b)
{
    return a.mutari > b.mutari;
}

void del(int poz = 1)
{
    if(poz == nrel)
    {
        --nrel;
        return ;
    }

    swap(h[poz], h[nrel]);
    --nrel;

    sift(poz);
}
int main()
{
    int n, x, l, i, d, maxmut = 0;
    fin >> n >> x >> l;
    maxmut = x / l;
    for(i = 1; i <= n; ++i)
    {
        fin >> d >> w[i].lana;
        w[i].mutari = (x - d) / l;
    }

    sort(w+1, w+1+n, comp);

    int j = 1;
    for(i = maxmut; i >= 0; --i)
    {
        while(j <= n && w[j].mutari == i)
        {
            add(w[j].lana);
            ++j;
        }

        if(nrel > 0)
        {
            sum += root();
            del();
        }

    }

    fout << sum;
    return 0;
}