Cod sursa(job #585667)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 aprilie 2011 10:51:35
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.29 kb
#include <cstdio>
#include <queue>
#define mp make_pair

using namespace std;

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

const int N = 50005;

bool used[2 * N];

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(mp(ta[i], mp(ta[i], 0)));

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

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

void solve() {
    pair <int, 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) {
            used[tpa.second.second] = 1;
            tpb = Hb.top();
            Hb.pop();

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

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

        }

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

    used[0] = 1;

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

        if (! used[tpa.second.second]) {
            tpb = Hb.top();
            Hb.pop();

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

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

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

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