Cod sursa(job #586053)

Utilizator katakunaCazacu Alexandru katakuna Data 30 aprilie 2011 13:30:22
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 3.2 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string.h>
#include <set>
using namespace std;

#define Nmax 100010
#define Mmax 50010

#define INF 0x3f3f3f3f

int n, Na, Nb;
int A[Mmax], B[Mmax], T[Nmax], Sol[Nmax];

int H1[Nmax], H2[Nmax];
int Cst[Nmax];
int N1, N2;

void up_heap1 (int p) {

    int t, c = p, aux;
    t = c >> 1;

    while (t && Cst[ H1[t] ] + A[ H1[t] ] > Cst[ H1[c] ] + A[ H1[c] ]) {
        aux = H1[t];
        H1[t] = H1[c];
        H1[c] = aux;

        c = t;
        t = c >> 1;
    }
}

void up_heap2 (int p) {

    int t, c = p, aux;
    t = c >> 1;

    while (t && A[ H2[t] ] > A[ H2[c] ]) {
        aux = H2[t];
        H2[t] = H2[c];
        H2[c] = aux;

        c = t;
        t = c >> 1;
    }
}

void down_heap1 (int p) {

    int t = p, c, aux;
    c = t << 1;

    if (c < N1 && Cst[ H1[c + 1] ] + A[ H1[c + 1] ] < Cst[ H1[c + 1] ] + A[ H1[c + 1] ]) c++;

    while (c <= N1 && Cst[ H1[t] ] + A[ H1[t] ] > Cst[ H1[c] ] + A[ H1[c] ]) {
        aux = H1[t];
        H1[t] = H1[c];
        H1[c] = aux;

        t = c;
        c = t << 1;
        if (c < N1 && Cst[ H1[c + 1] ] + A[ H1[c + 1] ] < Cst[ H1[c + 1] ] + A[ H1[c + 1] ]) c++;
    }
}

void down_heap2 (int p) {

    int t = p, c, aux;
    c = t << 1;

    if (c < N2 && A[ H2[c + 1] ] < A[ H2[c + 1] ]) c++;

    while (c <= N2 && A[ H2[t] ] > A[ H2[c] ]) {
        aux = H2[t];
        H2[t] = H2[c];
        H2[c] = aux;

        t = c;
        c = t << 1;
        if (c < N2 && A[ H2[c + 1] ] < A[ H2[c + 1] ]) c++;
    }
}

void rezolva () {

    int i, c1, c2;

    sort (T + 1, T + n + 1);

    N1 = N2 = 0;
    for (i = 1; i <= Na; i++) {
        H1[++N1] = i;
        Cst[i] = 0;
        up_heap1 (N1);
    }

    for (i = 1; i <= n; i++) {
        while (N1 && Cst[ H1[1] ] < T[i]) {

            H2[++N2] = H1[1];
            up_heap2 (N2);

            H1[1] = H1[N1];
            N1--;
            down_heap1 (1);
        }

        c1 = INF; c2 = INF;
        if (N1)
            c1 = Cst[H1[1]] + A[ H1[1] ];

        if (N2)
            c2 = T[i] + A[ H2[1] ];

        if (c1 <= c2) {
            Sol[i] = c1;
            Cst[ H1[1] ] = c1;
            down_heap1 (1);
        }
        else {
            Sol[i] = c2;
            Cst[ H2[1] ] = c2;

            if ( Cst[ H2[1] ] > T[i + 1] && i < n ) {
                H1[ ++N1 ] = H2[1];
                up_heap1 (N1);

                H2[1] = H2[N2];
                N2--;
                down_heap2 (1);
            }
            else {
                down_heap2 (1);
            }
        }
    }
}

void citire () {

    int i;
    scanf ("%d %d %d", &n, &Na, &Nb);

    for (i = 1; i <= Na; i++)
        scanf ("%d", &A[i]);

    for (i = 1; i <= Nb; i++)
        scanf ("%d", &B[i]);
}

int main () {

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

    citire ();

    rezolva ();
    memcpy (T, Sol, sizeof (Sol));

    int i;
    long long sol = 0;

    for (i = 1; i <= n; i++)
        if (sol < Sol[i]) sol = Sol[i];
    printf ("%lld ", sol);

    Na = Nb;
    mempcpy (B, A, sizeof (B)); //

    rezolva ();

    sol = 0;
    for (i = 1; i <= n; i++)
        if (sol < Sol[i]) sol = Sol[i];
    printf ("%lld\n", sol);

    return 0;
}