Cod sursa(job #2408774)

Utilizator robertrRotaru Stefan Robert robertr Data 18 aprilie 2019 12:35:05
Problema Lupul Urias si Rau Scor 52
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("lupu.in");
ofstream g("lupu.out");
int m,l,x,H[100005],n,lm;
long long s;
struct oaie
{
    int timp,lana;
}v[100001];
inline bool comp(oaie a,oaie b)
{
    return a.timp>b.timp;
}
void hins(int x)
{
    int fiu=++n,tata=n/2;
    while(tata&&H[tata]<x)
    {
        H[fiu]=H[tata];
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
}
void hcomb(int i,int n)
{
    int val=H[i],tata=i,fiu=2*i;
    while(fiu<=n)
    {
        if(fiu<n&&H[fiu]<H[fiu+1]) fiu++;
        if(val<H[fiu])
        {
            H[tata]=H[fiu];
            tata=fiu;
            fiu*=2;
        }
        else fiu=n+1;
    }
    H[tata]=val;
}
int extr()
{
    if(!n) return 0;
    int val=H[1];
    H[1]=H[n--];
    hcomb(1,n);
    return val;
}
int main()
{
    f>>m>>l>>x;
    for(int i=1;i<=m;i++)
    {
        int d;
        f>>d>>v[i].lana;
        if(d<=l)
            v[i].timp=(l-d)/x+1;
    }
    sort(v+1,v+m+1,comp);
    v[m+1].timp=99999999;
    int tmax=v[1].timp;
    for(int i=1;i<=m+1;i++)
    {
        if(v[i].timp==tmax)
            hins(v[i].lana);
        else
        {
            s+=extr();
            tmax--;
            hins(v[i].lana);
        }
    }
    g<<s<<'\n';
    return 0;
}