Cod sursa(job #2832239)

Utilizator TraianQTraianQ TraianQ Data 13 ianuarie 2022 11:00:36
Problema Lupul Urias si Rau Scor 88
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <algorithm>
#define LL long long
using namespace std;
struct Oaie
{
    LL lana,timp;
}v[100005];
LL H[100005],lh;
void add(LL 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;
    }
}
bool cmp(Oaie a,Oaie b)
{
    return a.timp>b.timp;
}
int main()
{
    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
    LL 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);
    long long j=1,suml=0;
    for(int i=maxt;i>=1;i--)
    {
        while(j<=n && v[j].timp==i)
            add(v[j++].lana);
        if(lh)
        suml+=H[1];
        del();
    }
    cout<<suml;
    return 0;
}