Cod sursa(job #1924135)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 12 martie 2017 11:44:57
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream fin ("fabrica.in"); ofstream fout ("fabrica.out");

typedef long long i64;

const int nmax = 1e5;
const int mmax = 5e4;

i64 t1[nmax + 1], t2[nmax + 1];
int a[mmax + 1], b[mmax + 1];

struct str{
    int ind; i64 t;

    str() {}
    str (int _ind, i64 _t) {
        ind = _ind, t = _t;
    }

    inline bool operator < (const str &x) const {
        return (t > x.t);
    }
};
priority_queue< str > q;

int main() {
    int n, nra, nrb;
    fin >> n >> nra >> nrb;

    for (int i = 1; i <= nra; ++ i) {
        fin >> a[ i ];
    }
    for (int i = 1; i <= nrb; ++ i) {
        fin >> b[ i ];
    }

    for (int i = 1; i <= nra; ++ i) {
        q.push(str(i, a[ i ]));
    }

    for (int i = 1; i <= n; ++ i) {
        t1[ i ] = q.top().t;
        str aux = q.top(); q.pop();
        q.push(str(aux.ind, aux.t + a[ aux.ind ]));
    }

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

    for (int i = 1; i <= nrb; ++ i) {
        q.push(str(i, b[ i ]));
    }

    for (int i = 1; i <= n; ++ i) {
        t2[ i ] = q.top().t;
        str aux = q.top(); q.pop();
        q.push(str(aux.ind, aux.t + b[ aux.ind ]));
    }

    i64 ans = 0;
    for (int i = 1; i <= n; ++ i) {
        ans = max(ans, t1[ i ] + t2[n - i + 1]);
    }

    fout << t1[ n ] << " " << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}