Cod sursa(job #1465997)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 28 iulie 2015 13:45:37
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <algorithm>
#define NMAX 100001
#define MIN -1

using namespace std;

ifstream f("lupu.in");
ofstream g("lupu.out");

int i, n = 0, x, l, m, timp = 0, ans = 0;

struct oaie
{
    int dist, lana;
};
oaie heap[NMAX], a;

int father(int x)
{
    return x/2;
}

int left_son(int x)
{
    return 2*x;
}

int right_son(int x)
{
    return 2*x + 1;
}

void get_down(int k)
{
    int aux;

    do
    {
        if (left_son(k) <= n)
            aux = left_son(k);

        if (right_son(k) <= n && heap[right_son(k)].lana > heap[aux].lana)
            aux = right_son(k);

        if (heap[right_son(k)].lana < heap[k].lana && heap[left_son(k)].lana < heap[k].lana)
            aux = 0;

        if (aux)
        {
            swap(heap[aux], heap[k]);
            k = aux;
        }
    }while (aux);
}

void get_up(int k)
{
    while (k > 1 && heap[k].lana > heap[father(k)].lana)
    {
        swap(heap[k], heap[father(k)]);
        k = father(k);
    }
}

void insert_heap(oaie x)
{
    heap[++n] = x;
    get_up(n);
}

void delete_heap(int k)
{
    heap[k] = heap[n];
    heap[n].lana = MIN;
    n --;
    get_down(k);
}

int main()
{
    f >> m >> x >> l;

    for (i=1; i<=m; ++i)
    {
        f >> a.dist >> a.lana;
        insert_heap(a);
    }

    while (n)
    {
        if (heap[1].dist + timp * l <= x)
        {
            timp ++;
            ans += heap[1].lana;
            delete_heap(1);
        }
        else
            delete_heap(1);
    }

    g << ans << '\n';
    return 0;
}