Cod sursa(job #585639)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 aprilie 2011 10:32:12
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.81 kb
#include <cstdio>
#include <queue>

using namespace std;

priority_queue <pair <int,int>, vector <pair <int, int> >, greater <pair <int, int> > > Ha, Hb;

const int N = 50005;

int n, na, nb, ta[N], tb[N];

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

    scanf("%d%d%d", &n, &na, &nb);

    for (int i = 1; i <= na; ++ i)
        scanf("%d", &ta[i]);

    for (int i = 1; i <= nb; ++ i)
        scanf("%d", &tb[i]);
}

void init() {
    for (int i = 1; i <= na; ++ i)
        Ha.push(make_pair(0, ta[i]));

    for (int i = 1; i <= nb; ++ i)
        Hb.push(make_pair(0, tb[i]));
}

int max(int x, int y) {
    return x > y ? x : y;
}

void solve() {
    pair <int, int> tpa, tpb;
    int tma = - 1, tmb = - 1;

    for (int i = 1; i <= n; ++ i) {
        tpa = Ha.top();
        Ha.pop();

        if (tpa.first) {
            tpb = Hb.top();
            Hb.pop();

            Hb.push(make_pair(max(tpa.first, tpa.first) + tpb.second, tpb.second));

            if (max(tpa.first, tpa.first) + tpb.second > tmb)
                tmb = max(tpa.first, tpa.first) + tpb.second;

        }

        Ha.push(make_pair(tpa.first + tpa.second, tpa.second));
        if (tpa.first + tpa.second > tma)
            tma = tpa.first + tpa.second;
    }

    while (! Ha.empty()) {
        tpa = Ha.top();
        Ha.pop();

        if (tpa.first) {
            tpb = Hb.top();
            Hb.pop();

            Hb.push(make_pair(max(tpa.first, tpa.first) + tpb.second, tpb.second));

            if (max(tpa.first, tpa.first) + tpb.second > tmb)
                tmb = max(tpa.first, tpa.first) + tpb.second;

        }
    }
    printf("%d %d\n", tma, tmb);
}

int main() {
    read();
    init();
    solve();
    return 0;
}