Cod sursa(job #2401938)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 10 aprilie 2019 11:00:10
Problema Fabrica Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream>
#include<algorithm>
#define DIM 50005
#define DIM2 100005
#define f first
#define s second
using namespace std;
int n, a, b, i, maxim;
int va[DIM], vb[DIM], t[DIM2];
pair<int, int> h[DIM];
ifstream fin("fabrica.in");
ofstream fout("fabrica.out");
void elim(int n){
    int p = 1, c = 2;
    while(c <= n){
        if(c + 1 <= n && h[c].f > h[c + 1].f){
            c++;
        }
        if(h[p].f > h[c].f){
            swap(h[p], h[c]);
            p = c;
            c = p + p;
        }
        else{
            break;
        }
    }
}
int main(){
    fin>> n >> a >> b;
    for(i = 1; i <= a; i++){
        fin>> va[i];
    }
    for(i = 1; i <= b; i++){
        fin>> vb[i];
    }
    sort(va + 1, va + a + 1);
    sort(vb + 1, vb + b + 1);
    for(i = 1; i <= a; i++){
        h[i] = make_pair(va[i], i);
    }
    for(i = 1; i <= n; i++){
        t[i] = h[1].f;
        h[1].f += va[ h[1].s ];
        elim(a);
    }
    for(i = 1; i <= b; i++){
        h[i] = make_pair(vb[i], i);
    }
    for(i = n; i >= 1; i--){
        maxim = max(maxim, t[i] + h[1].f);
        h[1].f += va[ h[1].s ];
        elim(b);
    }
    fout<< t[n] <<" "<< maxim <<"\n";
    return 0;
}