Cod sursa(job #1992425)

Utilizator giotoPopescu Ioan gioto Data 20 iunie 2017 14:20:02
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <set>
using namespace std;

int x, n, nra, nrb, L, Heap[100005], p[100005], t[100005], aux[100005];
multiset <int> ma;
multiset <int> mb;
inline void pop(int x){
    int y = 0;
    while(x != y){
        y = x;
        if(y * 2 <= L && t[Heap[y * 2]] < t[Heap[x]]) x = y * 2;
        if(y * 2 + 1 <= L && t[Heap[y * 2 + 1]] < t[Heap[x]]) x = y * 2 + 1;
        int aux = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = aux;
    }
}
inline void push(int x){
    while(x / 2 && t[Heap[x]] < t[Heap[x / 2]]){
        int aux = Heap[x];
        Heap[x] = Heap[x / 2];
        Heap[x / 2] = aux;
        x /= 2;
    }
}
int main()
{
    freopen("fabrica.in", "r", stdin);
    freopen("fabrica.out", "w", stdout);
    scanf("%d%d%d", &n, &nra, &nrb);
    for(int i = 1; i <= nra ; ++i){
        scanf("%d", &x);
        ma.insert(x);
    }
    for(int i = 1; i <= nrb ; ++i){
        scanf("%d", &x);
        mb.insert(x);
    }
    multiset <int> :: iterator it;
    int time = 0, nr = 0;
    for(int i = 1; i <= n ; ++i){
        int cr = time;
        if(!ma.empty()){
            it = ma.begin();
            cr = *it + time;
        }
        if((ma.empty() || (cr) > t[Heap[1]]) && L > 0){
            time = t[Heap[1]];
            while(L > 0 && (t[Heap[1]] <= time || t[Heap[1]] <= cr)){
                ma.insert(aux[Heap[1]]);
                Heap[1] = Heap[L--];
                pop(1);
            }
        }
        it = ma.begin();
        p[i] = time + (*it);
        Heap[++L] = ++nr;
        aux[nr] = *it;
        t[nr] = *it + time;
        ma.erase(it);
    }
    int Sol = p[1];
    for(int i = 2; i <= n ; ++i) if(p[i] > Sol) Sol = p[i];
    printf("%d ", Sol);
    L = 0; time = 0; nr = 0;
    for(int i = n; i >= 1 ; --i){
        int cr = time;
        if(!mb.empty()){
            it = mb.begin();
            cr = *it + time;
        }
        if((mb.empty() || (cr) > t[Heap[1]]) && L > 0){
            time = t[Heap[1]];
            while(L > 0 && (t[Heap[1]] <= time || t[Heap[1]] <= cr)){
                mb.insert(aux[Heap[1]]);
                Heap[1] = Heap[L--];
                pop(1);
            }
        }
        it = mb.begin();
        p[i] += time + (*it);
        Heap[++L] = ++nr;
        aux[nr] = *it;
        t[nr] = *it + time;
        mb.erase(it);
    }
    Sol = p[1];
    for(int i = 2; i <= n ; ++i) if(p[i] > Sol) Sol = p[i];
    printf("%d", Sol);
    return 0;
}