Cod sursa(job #2019612)

Utilizator antanaAntonia Boca antana Data 8 septembrie 2017 10:09:22
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 1;
const int MAXP = 5 * 1e4 + 1;

FILE *fin, *fout;

struct Can {
    int idx, tmp;

    bool operator < (const Can &aux) const {
        return (tmp > aux.tmp);
    }
};

priority_queue < Can > heap;

int n, na, nb, a[MAXP], b[MAXP], p1[MAXN], p2[MAXN];

int main()
{
    fin = fopen( "fabrica.in", "r" );
    fout= fopen( "fabrica.out","w" );

    fscanf(fin, "%d%d%d", &n, &na, &nb);

    for (int i = 1; i <= na; i++)
        fscanf(fin, "%d", &a[ i ]);
    for (int i = 1; i <= nb; i++)
        fscanf(fin, "%d", &b[ i ]);

    for (int i = 1; i <= na; i++)
        heap.push( {i, a[ i ]} );

    for (int i = 1; i <= n; i++) {
        p1[ i ] = heap.top().tmp;
        Can aux = heap.top();
        heap.pop();
        heap.push( {aux.idx, aux.tmp + a[ aux.idx ]} );
    }

    while(!heap.empty())
        heap.pop();

    for (int i=1; i <= nb; i++)
        heap.push( {i, b[ i ]} );
    for (int i=1; i <= n; i++) {
        p2[ i ] = heap.top().tmp;
        Can aux = heap.top();
        heap.pop();
        heap.push( {aux.idx, aux.tmp + b[ aux.idx ]} );
    }

    int ans = 0;
    for (int i=1; i<=n; i++)
        ans = max( ans, p1[ i ] + p2[ n - i + 1] );
    fprintf(fout, "%d %d", p1[ n ], ans);

    fclose( fin );
    fclose( fout );

    return 0;
}