Cod sursa(job #1993676)

Utilizator giotoPopescu Ioan gioto Data 23 iunie 2017 15:54:55
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <algorithm>
using namespace std;

int x, n, nra, nrb, L, Heap[100005], a[100005], t[100005], b[100005], p[100005], aux[100005];
inline void push(int L){
    while(t[Heap[L]] < t[Heap[L / 2]]){
        int aux = Heap[L];
        Heap[L] = Heap[L / 2];
        Heap[L / 2] = aux;
        L = L / 2;
    }
}
inline void pop(int x){
    int y = 0;
    while(x != y){
        y = x;
        if(y * 2 <= L && t[Heap[x]] > t[Heap[y * 2]]) x = y * 2;
        if(y * 2 + 1 <= L && t[Heap[x]] > t[Heap[y * 2 + 1]]) x = y * 2 + 1;
        int aux = Heap[x];
        Heap[x] = Heap[y];
        Heap[y] = aux;
    }
}
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", &a[i]);
        Heap[i] = i;
        t[i] = a[i];
        ++L;
        push(L);
    }
    int Sol = 0;
    for(int i = 1; i <= n ; ++i){
        p[i] = t[Heap[1]];
        t[Heap[1]] += a[Heap[1]];
        pop(1);
        if(p[i] > Sol) Sol = p[i];
    }
    printf("%d", Sol);
    L = 0;
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= nrb ; ++i){
        scanf("%d", &b[i]);
        Heap[i] = i;
        t[i] = b[i];
        ++L;
        push(L);
    }
    Sol = 0;
    for(int i = n; i >= 1 ; --i){
        p[i] += t[Heap[1]];
        t[Heap[1]] += b[Heap[1]];
        pop(1);
        if(p[i] > Sol) Sol = p[i];
    }
    printf(" %d", Sol);
    return 0;
}