Cod sursa(job #585645)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 aprilie 2011 10:36:35
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.95 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(ta[i], ta[i]));

    for (int i = 1; i <= nb; ++ i)
        Hb.push(make_pair(tb[i], 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.second, tpb.first - tpb.second) + 2 * tpb.second, tpb.second));

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

        }

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

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

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

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

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

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

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