Cod sursa(job #2401881)

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