Cod sursa(job #3173250)

Utilizator cristianabalcanuCristiana Balcanu cristianabalcanu Data 22 noiembrie 2023 10:22:30
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
#define NN 100005
using namespace std;
ifstream fin ("lupul.in");
ofstream fout ("lupul.out");

struct Oi
{
    int pasi, blana;
};

int n, dmax, lenpas;
int a, b, pasi, pasimax, suma, blana, hsize, h[NN];
Oi v[NN];

void push_up(int p)
{
    int pp;
    while(p / 2 >= 1)
    {
        pp = p / 2;
        if(h[pp] >= h[p])
            return;
        swap(h[p], h[pp]);
        p = pp;
    }
}

void push_down(int p)
{
    int pp;
    while(p * 2 <= hsize)
    {
        pp = p * 2;
        if(pp + 1 <= hsize && h[pp + 1] > h[pp])
            pp++;
        if(h[pp] <= h[p])
            return;
        swap(h[p], h[pp]);
        p = pp;
    }
}

bool compara(Oi a, Oi b)
{
    return a.pasi > b.pasi;
}

int main()
{
    fin >> n >> dmax >> lenpas;
    for(int i = 1 ; i <= n ; i++)
    {
        fin >> a >> v[i].blana;
        v[i].pasi = 1 + (dmax - a) / lenpas;
        pasimax = max(pasimax, v[i].pasi);
    }
    sort(v + 1, v + 1 + n, compara);
    for(int i = 1 ; i <= n ; i++)
    {
        if(v[i].pasi != pasimax)
        {
            suma += h[1];
            h[1] = h[hsize];
            h[hsize] = 0;
            hsize--;
            push_down(1);
            pasimax = v[i].pasi;
        }
        hsize++;
        h[hsize] = v[i].blana;
        push_up(hsize);
    }
    suma += h[1];
    fout << suma;

    return 0;
}