Cod sursa(job #1466021)

Utilizator crysstyanIacob Paul Cristian crysstyan Data 28 iulie 2015 14:36:26
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>
#define NMAX 200005
#define MIN -1
#define INF (1 << 31) - 1

using namespace std;

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

int i, n = 0;
long long ans = 0, x, l, m, timp = 0, tmax = -1;
bool visited[NMAX];

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

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
    {
        aux = 0;

        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;
  //  heap[n].dist = INF;
    n --;
    get_down(k);
}

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

    for (i=1; i<=m; ++i)
    {
        f >> a[i].dist >> a[i].lana;
        tmax = max(tmax, (x - a[i].dist) / l);
    }


    do
    {
        tmax = -1;
        n = 0;

        for (i=1; i<=m; ++i)
            if (a[i].dist + timp * l > x - l && a[i].dist + timp * l <= x)
                insert_heap(a[i]);

        if (n)
            ans += (long long) heap[1].lana, timp++;
    }
    while (n);

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