Cod sursa(job #1399106)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 24 martie 2015 16:10:24
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
#include <vector>

#define father(x) x / 2
#define left_son(x) 2 * x
#define right_son(x) 2 * x + 1

using namespace std;

fstream f("lupu.in", ios::in);
fstream g("lupu.out", ios::out);

const int nmax = 100010;

int a[nmax], t[nmax], h[nmax], n, d, l, tmax, i, j, nr;
long long sum;

void read()
{
    int pas, dist, lana;
    f >> n >> d >> l;
    tmax = 0;
    for (i = 1; i <= n; i++)
    {
        f >> dist >> lana;
        pas = 1 + (d - dist)/l;
        a[i] = lana;
        t[i] = pas;
        if (pas > tmax) tmax = pas;
    }
}

void swap(int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
}

void up(int nod)
{
    while ((nod > 1) && (h[nod] > h[father(nod)]))
    {
        swap(nod, father(nod));
        nod = father(nod);
    }
}

void down(int nod)
{
    int ch = 1, son;
    while ((nod <= nr) && (left_son(nod) <= nr) && (ch))
    {
        ch = 0;
        son = left_son(nod);
        if ((right_son(nod) <= nr) && (h[right_son(nod)] > h[son])) son = right_son(nod);
        if (h[son] > h[nod])
        {
            ch = 1;
            swap(nod, son);
            nod = son;
        }
    }
}

void solve()
{
    int poz = 1;
    for (i = tmax; i >= 1; i--)
    {
        while (t[poz] == i)
        {
            nr++;
            h[nr] = a[poz];
            up(nr);
            poz++;
        }
        sum += h[1];
        h[1] = h[nr];
        nr--;
        down(1);
    }
}

void quickSort(int li, int ls)
{
    int i = li, j = ls, aux;
    int mij = t[(i + j) / 2];
    while (i <= j)
    {
        while (t[i] > mij) i++;
        while (t[j] < mij) j--;
        if (i <= j)
        {
            aux = t[i];
            t[i] = t[j];
            t[j] = aux;
            aux = a[i];
            a[i] = a[j];
            a[j] = aux;
            i++; j--;
        }
    }
    if (li < j) quickSort(li, j);
    if (i < ls) quickSort(i, ls);
}

int main()
{
    read();
    quickSort(1, n);
    solve();
    g << sum;
    return 0;
}