Cod sursa(job #1347184)

Utilizator Ionut228Ionut Calofir Ionut228 Data 18 februarie 2015 20:36:32
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("fabrica.in");
ofstream fout("fabrica.out");

int N, NRA, NRB;
int bereA[100005], bereB[100005];
int solA, solB;
int lgA, lgB;

struct heap
{
    int val, valinit;
};
heap A[100005], B[100005];

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

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

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

void urca(heap H[], int nod)
{
    while (nod > 1 && H[nod].val < H[father(nod)].val)
    {
        swap(H[nod], H[father(nod)]);
        nod = father(nod);
    }
}

void coboara(heap H[], int lg, int nod)
{
    int son = 1;
    while (son)
    {
        son = 0;
        if (left_son(nod) <= lg)
        {
            son = left_son(nod);
            if (right_son(nod) <= lg && H[right_son(nod)].val < H[son].val)
                    son = right_son(nod);

            if (H[son].val >= H[nod].val)
                son = 0;

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

void insert(heap H[], int& lg, int val, int valinit)
{
    ++lg;
    H[lg].val = val;
    H[lg].valinit = valinit;
    urca(H, lg);
}

void cut(heap H[], int& lg, int nod)
{
    H[nod] = H[lg];
    --lg;

    coboara(H, lg, nod);
}

int main()
{
    fin >> N >> NRA >> NRB;

    for (int i = 1, x; i <= NRA; ++i)
    {
        fin >> x;
        insert(A, lgA, x, x);
    }
    for (int i = 1; i <= N; ++i)
    {
        bereA[i] = A[1].val;
        insert(A, lgA, A[1].val + A[1].valinit, A[1].valinit);
        cut(A, lgA, 1);
    }

    for (int i = 1, x; i <= NRB; ++i)
    {
        fin >> x;
        insert(B, lgB, x, x);
    }
    for (int i = 1; i <= N; ++i)
    {
        bereB[i] = B[1].val;
        insert(B, lgB, B[1].val + B[1].valinit, B[1].valinit);
        cut(B, lgB, 1);
    }

    for (int i = 1; i <= N; ++i)
    {
        solA = max(solA, bereA[i]);
        solB = max(solB, bereA[i] + bereB[N - i + 1]);
    }

    fout << solA << ' ' << solB << '\n';

    fin.close();
    fout.close();
    return 0;
}