Cod sursa(job #1027952)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 13 noiembrie 2013 12:17:12
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct oaie
{
    int d, l;
};

const int N = 100000;

int h [N + 1];
oaie o [N + 1];
int n, dM, dep, dH, oMM;

bool oDD (const oaie a, const oaie b)
{
    return a. d > b. d;
}

int getOMM ()
{
    int i, nrO;

    for (i = 1; i <= n; i ++)
        if (o [i]. d <= dM)
            nrO ++;
    if (nrO >= dM / dep + 1)
        return dM / dep + 1;
    return nrO;
}

void init ()
{
    int i;

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

    scanf ("%d %d %d", & n, & dM, & dep);

    for (i = 1; i <= n; i ++)
        scanf ("%d %d", & o [i]. d, & o [i]. l);

    sort (o + 1, o + n + 1, oDD);

    oMM = getOMM ();
}

bool poate (int elem, int timp)
{
    if (o [elem]. d + timp * dep > dM)
        return false;
    return true;
}

void schimba (int p1, int p2)
{
    int aux = h [p1];
    h [p1] = h [p2];
    h [p2] = aux;
}

void urca (int p)
{
    while (p != 1 && h [p] < h [p / 2])
    {
        schimba (p, p / 2);
        p /= 2;
    }
}

void adauga (int elem)
{
    h [++ dH] = o [elem]. l;
    urca (dH);
}

void coboara (int p)
{
    int fs = 2 * p, fd = 2 * p + 1, bun = p;

    if (fs <= dH && h [fs] < h [bun])
        bun = fs;
    if (fd <= dH && h [fd] < h [bun])
        bun = fd;
    if (bun !=p)
    {
        schimba (h [p], h [bun]);
        coboara (bun);
    }
}

void sterge (int p)
{
    schimba (p, dH --);

    urca (p);
    coboara (p);
}

void rezolva ()
{
    int i, t = 0;

    for (i = 1; i <= n; i ++)
    {
        if (poate (i, t))
        {
            adauga (i);
            t ++;
        }
        else
            if (o [i]. l > h [1])
            {
                sterge (1);
                adauga (i);
            }
    }

    while (dH > oMM)
        sterge (h [1]);
}

void afis ()
{
    int i;
    long long s = 0;

    for (i = 1; i <= dH; i ++)
        s += (long long) h [i];

    printf ("%lld", s);
}

int main ()
{
    init ();
    rezolva ();
    afis ();

    return 0;
}