Cod sursa(job #2832210)

Utilizator TraianQTraianQ TraianQ Data 13 ianuarie 2022 10:28:17
Problema Lupul Urias si Rau Scor 72
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct Oaie
{
    int lana,timp;
}v[1000005];
int H[1000005],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;
}