Cod sursa(job #2877456)

Utilizator alexboat10759Alex Mateescu alexboat10759 Data 24 martie 2022 19:19:24
Problema Lupul Urias si Rau Scor 72
Compilator cpp-64 Status done
Runda concursceva2 Marime 1.28 kb
#include <fstream>
#include <algorithm>

using namespace std;
struct Oaie
{
    int lana,timp;
} v[100005];

int H[100005], lh;

void add(int x)
{
    H[++lh] = x;
    int clh = lh;
    while(H[clh/2]<H[clh] && clh>1)
    {
        swap(H[clh / 2], H[clh]);
        clh /= 2;
    }
}
void del()
{
    swap(H[1], H[lh]);
    lh--;
    int clh = 1;
    while(1)
    {
        int best = clh;
        if(2 * clh <= lh && H[2 * clh] > H[best])
            best=2 * clh;
        if(2 * clh + 1<=lh && H[2 * clh + 1] > H[best])
            best = 2 * clh + 1;
        if(best == clh)
            break;
        else
            swap(H[clh],H[best]),clh=best;
    }
}
int cmp(Oaie a, Oaie b)
{
    return a.timp > b.timp;
}
int main()
{
    ifstream cin("lupu.in");
    ofstream cout("lupu.out");

    int n, x, l, lana, timp, dist, maxt=0;
    cin>>n>>x>>l;
    for(int i = 1; i <= n; i++)
    {
        cin>>dist>>v[i].lana;
        v[i].timp = (x-dist) / l + 1;
        maxt = max(maxt,v[i].timp);
    }
    sort(v + 1, v + n + 1, cmp);
    int j = 1, suml = 0;
    for(int i = maxt; i >= 1; i--)
    {
        while(j <= n && v[j].timp == i)
            add(v[j++].lana);
        suml += H[1];
        del();
    }
    cout<<suml;
    return 0;
}