Cod sursa(job #585673)

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

#define Nmax 100010
#define Mmax 50010

struct HEAP {
    long long t;
    int nod;
} H[Mmax], aux;

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

void up_heap (int p) {

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

    while ( t &&  H[t].t > H[c].t) {
        aux = H[t];
        H[t] = H[c];
        H[c] = aux;

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

void down_heap (int p) {

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

    if (c < Nh && H[c + 1].t < H[c].t) c++;

    while (c <= Nh && H[t].t > H[c].t) {
        aux = H[t];
        H[t] = H[c];
        H[c] = aux;

        t = c;
        c = t << 1;
        if (c < Nh && H[c + 1].t < H[c].t) c++;
    }
}

void rezolva (long long T[], int N, int A[]) {

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

    int i;
    Nh = 0;
    for (i = 1; i <= N; i++) {
        H[++Nh].t = A[i];
        H[Nh].nod = i;
        up_heap (Nh);
    }

    for (i = 1; i <= n; i++) {
        Sol[i] = H[1].t;
        // Incepe in H[1].t - A[ H[1].nod ];
        if (H[1].t - A[ H[1].nod ] < T[i]) Sol[i]+= T[i] - (long long)(H[1].t - (long long)A[ H[1].nod ]);
        H[1].t =  Sol[i] + (long long) A[ H[1].nod ];
        down_heap (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 (T, Na, A);
    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);

    rezolva (T, Nb, B);

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

    return 0;
}