Cod sursa(job #2036174)

Utilizator RaduToporanRadu Toporan RaduToporan Data 10 octombrie 2017 13:54:45
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
struct oaie{
    int cant;
    int strat;
};
int n,x,st,l,i,j,d,a,nrel,h[100005];
long long total;
oaie v[100005];

bool cmp(oaie a, oaie b)
{
    if (a.strat<b.strat) return 1;
        else return 0;
}

void urca()
{
    int poz=nrel;
    while (poz>1 && h[poz]>h[poz/2])
    {
        swap(h[poz],h[poz/2]);
        poz=poz/2;
    }
}

void coboara()
{
    int poz=1;
    while (h[2*poz]>h[poz] or h[2*poz+1]>h[poz])
    {
        if (h[2*poz]>h[poz] && 2*poz<=nrel)
        {
            swap(h[2*poz],h[poz]);
            poz=2*poz;
        }
        else if (2*poz+1<=nrel)
            {
                swap(h[2*poz+1],h[poz]);
                poz=2*poz+1;
            }
    }
}

int main()
{
    freopen("lupu.in","r",stdin);
    freopen("lupu.out","w",stdout);
    scanf("%d%d%d",&n,&x,&l);
    for (i=1; i<=n; i++)
    {
        scanf("%d%d",&d,&a);
        v[i].cant=a;
        v[i].strat=d+l-1/l;
    }
    sort(v+1,v+n+1,cmp);
    j=1;
    for (i=0; i<=x/l; i++)
    {
        //iau toate oile de pe stratul al i-lea si le bag in heap
        st=v[j].strat;
        while (j<=n && v[j].strat==st)
        {
            h[++nrel]=v[j++].cant;
            urca();
        }
        if (nrel>0) {total=total+1ll*h[1];
        h[1]=h[nrel--];}
        coboara();
    }
    printf("%lld\n",total);
    return 0;
}