Cod sursa(job #585954)

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

#define Nmax 100010
#define Mmax 50010

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

int n, Na, Nb, Nh;
int A[Mmax], B[Mmax];
int 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 (int 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;
        H[1].t =  Sol[i] + (long long) A[ H[1].nod ];
        down_heap (1);
    }
}

int cont (int X) {

    int i, j, x;
    for (i = 1, j = 1; i <= Nb; i++) {
        x = 0;
        if (T[j] > x) x = T[j];

        while (j <= n && x + B[i] <= X) {
            x+= B[i];
            j++;
            if (T[j] > x) x = T[j];
        }

        if (j > n) return 1;
    }

    return 0;
}

void cauta () {

    sort (T, T + n + 1);

    int p = 1, u = (1 << 30), mij, sol;
    while (p <= u) {
        mij = (p + u) >> 1;
        if ( cont (mij) ) {
            sol = mij;
            u = mij - 1;
        }
        else
            p = mij + 1;
    }

    printf ("%d ", sol);
}

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;
    int sol = 0;

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

    cauta ();

    return 0;
}