Cod sursa(job #609907)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 23 august 2011 19:43:50
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>

#define NMax 100005

using namespace std;

int ND, NA, NB, T[NMax], S1, S2;
int Heap[2][NMax], NH[2],Free[2][NMax];

inline int Max (int a, int b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

inline void Swap (int H, int X, int Y)
{
    int Aux;
    Aux=Heap[H][X];
    Heap[H][X]=Heap[H][Y];
    Heap[H][Y]=Aux;
}

void Percolate (int H, int X)
{
    int Father=X>>1;
    if (Father>0 and Free[H][Heap[H][Father]]>Free[H][Heap[H][X]])
    {
        Swap (H, X, Father);
        Percolate (H, Father);
    }
}

void Sift (int H, int X)
{
    int Son=X<<1;
    if (Son+1<=NH[H] and Free[H][Heap[H][Son+1]]<Free[H][Heap[H][Son]])
    {
        ++Son;
    }
    if (Son<=NH[H] and Free[H][Heap[H][Son]]<Free[H][Heap[H][X]])
    {
        Swap (H, X, Son);
        Sift (H, Son);
    }
}

void Insert (int H, int X)
{
    Heap[H][++NH[H]]=X;
    Percolate (H, NH[H]);
}

void Delete (int H, int X)
{
    Swap (H, X, NH[H]);
    Heap[H][NH[H]]=0;
    --NH[H];
    Sift (H, X);
}

void Process ()
{
    while (NH[0]>0)
    {
        int X=Heap[0][1];
        int P=Heap[1][1];
        Free[1][P]=Max (Free[0][X]+T[P], Free[1][P])+T[P];
        Free[0][X]=Free[1][P]-T[P];
        Sift (1, 1);
        Delete (0, 1);
    }
}

int main ()
{
    freopen ("fabrica.in", "r", stdin);
    freopen ("fabrica.out", "w", stdout);
    scanf ("%d %d %d\n", &ND, &NA, &NB);
    for (int i=1; i<=ND; ++i)
    {
        Insert (0, i);
    }
    for (int i=1; i<=NA; ++i)
    {
        scanf ("%d", &T[i]);
        Free[1][i]=T[i];
        Insert (1, i);
    }
    Process ();
    for (int i=1; i<=ND; ++i)
    {
        S1=Max (S1, Free[0][i]);
    }
    for (int i=1; i<=ND; ++i)
    {
        Insert (0, i);
    }
    while (NH[1]>0)
    {
        Delete (1, 1);
    }
    for (int i=1; i<=NB; ++i)
    {
        scanf ("%d", &T[i]);
        Free[1][i]=T[i];
        Insert (1, i);
    }
    Process ();
    for (int i=1; i<=ND; ++i)
    {
        S2=Max (S2, Free[0][i]);
    }
    printf ("%d %d\n", S1, S2);
    return 0;
}