Cod sursa(job #610820)

Utilizator vlad2901Vlad Berindei vlad2901 Data 29 august 2011 14:01:20
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100000

using namespace std;

struct oaie
{
    int nr, pas;
} t[NMAX];

int H[NMAX + 1], lh, a[NMAX], d[NMAX], n, x, l;

bool cmp(oaie x, oaie y)
{
    return x.pas < y.pas;
}

void percolate(int i)
{
    int curent = H[i];
    while(i>1 && a[H[i/2]] < a[curent])
    {
        H[i] = H[i/2];
        i /= 2;
    }
    H[i] = curent;
}

void stif(int i)
{
    int st, dr, son;
    do
    {
        st = 2*i;
        dr = 2*i + 1;
        son = 0;

        if(st < lh)
        {
            son = st;
            if(dr < lh && a[H[dr]] > a[H[st]])
            {
                son = dr;
            }
            if(a[H[son]] < a[H[i]])
            {
                son = 0;
            }
        }

        if(son)
        {
            swap(H[i], H[son]);
        }

        i = son;

    } while(son);
}

int main()
{
    int tmax = 0, i, curent, ok;
    long long sum = 0;

    freopen("lupu.in", "r", stdin);
    freopen("lupu.out", "w", stdout);

    scanf("%d %d %d", &n, &x, &l);

    //t[i].pas e numarul maxim de pasi dupa care poate fi prinsa oaia t[i].nr

    for(i=0;i<n;++i)
    {
        scanf("%d %d", &d[i], &a[i]);
         if(x - d[i] >= 0)
        {
            t[i].pas = (x - d[i]) / l + 1;
        }

        t[i].nr = i;
        if(tmax < t[i].pas)
        {
            tmax = t[i].pas;
        }
    }

    sort(t, t+n, cmp); //sortez dupa pas

    i = n-1;
    curent = tmax;
    lh = 0; //lungimea heap-ului (initial e gol)

    //parcurg t de la max la min
    while(curent > 0)
    {
        ok = 1;

        while(i >= 0 && t[i].pas == curent)
        {
            ok = 0;
            H[++lh] = t[i].nr;
            percolate(lh);

            --i;
        }
        //extrag maximul
        if(lh > 0)
        {
            sum += a[H[1]];
            H[1] = H[lh--];
            stif(1);
        }

        --curent;
    }

    printf("%lld", sum);

    return 0;
}