Cod sursa(job #585961)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 30 aprilie 2011 12:55:35
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.91 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], timpa[2 * 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]);
}

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

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

void solve_a() {
    pair <int, int> tpa;
    int tma = - 1;

    for (int i = 1; i <= na; ++ i)
        Ha.push(mp(ta[i], ta[i]));

    for (int i = 1; i <= n; ++ i) {
        tpa = Ha.top();
        Ha.pop();
        timpa[i] = tpa.first;
        Ha.push(mp(tpa.first + tpa.second, tpa.second));
        if (timpa[i] > tma)
            tma = timpa[i];
    }

    printf("%d ", tma);
}

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

priority_queue <int, vector <int>, greater <int> > H, T;

void solve_b() {
    pair <int, int> tpb;
    int curt, tmb = - 1;

    for (int i = 1; i <= n; ++ i)
        H.push(timpa[i]);

    for (int i = 1; i <= nb; ++ i)
        T.push(tb[i]);

    for (int i = 1; i <= n; ++ i) {
        curt = H.top();
        H.pop();
        while (! Hb.empty() && Hb.top().first - Hb.top().second <= curt) {
            T.push(Hb.top().second);
            Hb.pop();
        }
        if (Hb. empty()) {
            Hb.push(mp(curt + T.top() + T.top(), T.top()));
            if (curt + T.top() > tmb)
                tmb = curt + T.top();
            T.pop();
        } else {
            tpb = Hb.top();
            if (T.empty()) {
                Hb.pop();
                Hb.push(mp(max(curt + tpb.second, tpb.first) + tpb.second, tpb.second));
                if (max(curt + tpb.second, tpb.first) > tmb)
                    tmb = max(curt + tpb.second, tpb.first);
            } else {
                if (curt + T.top() < max(curt + tpb.second, tpb.first)) {
                    Hb. push(mp(curt + 2 * T.top(), T.top()));
                    if (curt + T.top() > tmb)
                        tmb = curt + T.top();
                    T.pop();
                } else {
                    Hb.pop();
                    Hb.push(mp(max(curt + tpb.second, tpb.first) + tpb.second, tpb.second));
                    if (max(curt + tpb.second, tpb.first) > tmb)
                        tmb = max(curt + tpb.second, tpb.first);
                }
            }
        }
    }

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

int main() {
    read();
    solve_a();
    solve_b();
    return 0;
}