Cod sursa(job #1536430)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 26 noiembrie 2015 10:03:23
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <cstdio>
#define MAXN 100000
#define MAXA 50000
int heap[MAXA], a[MAXA], b[MAXA];
long long v[MAXA], t[MAXN];
inline int tata(int p){
    return (p-1)/2;
}
inline int fiust(int p){
    return 2*p+1;
}
inline int fiudr(int p){
    return 2*p+2;
}
inline void swap(int p, int q){
    int aux=heap[p];
    heap[p]=heap[q];
    heap[q]=aux;
}
inline void coborare(int p, int n){
    int f=1, q;
    while((f)&&(fiust(p)<n)){
        q=fiust(p);
        if((fiudr(p)<n)&&(v[heap[fiudr(p)]]<v[heap[q]])){
            q=fiudr(p);
        }
        if(v[heap[q]]<v[heap[p]]){
            swap(p, q);
            p=q;
        }else{
            f=0;
        }
    }
}
inline void heapify(int n){
    for(int i=tata(n-1); i>=0; i--){
        coborare(i, n);
    }
}
int main(){
    int n, na, nb, i;
    long long x, y;
    FILE *fin, *fout;
    fin=fopen("fabrica.in", "r");
    fout=fopen("fabrica.out", "w");
    fscanf(fin, "%d%d%d", &n, &na, &nb);
    for(i=0; i<na; i++){
        fscanf(fin, "%d", &a[i]);
        v[i]=a[i];
        heap[i]=i;
    }
    heapify(na);
    x=0;
    for(i=0; i<n; i++){
        t[i]=v[heap[0]];
        v[heap[0]]+=a[heap[0]];
        coborare(0, na);
        if(x<t[i]){
            x=t[i];
        }
    }
    for(i=0; i<nb; i++){
        fscanf(fin, "%d", &b[i]);
        v[i]=b[i];
        heap[i]=i;
    }
    heapify(nb);
    y=0;
    for(i=n-1; i>=0; i--){
        t[i]+=v[heap[0]];
        v[heap[0]]+=b[heap[0]];
        coborare(0, nb);
        if(y<t[i]){
            y=t[i];
        }
    }
    fprintf(fout, "%lld %lld\n", x, y);
    fclose(fin);
    fclose(fout);
    return 0;
}