Cod sursa(job #1824268)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 7 decembrie 2016 17:17:19
Problema Fabrica Scor 68
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <cstdio>
#include <queue>
#define MAXN 50050

using namespace std;

unsigned int n, nra, nrb;
unsigned int a[MAXN], b[MAXN];
unsigned int ba[MAXN], bb[MAXN];
struct cmp
{
    unsigned int nr;
    unsigned int proc;
    cmp(unsigned int nr = 0, unsigned int proc = 0) : nr(nr), proc(proc) { }
    bool operator()(cmp x, cmp y)
    {
        return x.nr > y.nr;
    }
};
priority_queue<cmp, vector<cmp>, cmp> q;

void read()
{
    scanf("%d %d %d\n", &n, &nra, &nrb);
    for (unsigned int i = 1; i <= nra; i++)
        scanf("%d", &a[i]);
    for (unsigned int i = 1; i <= nrb; i++)
        scanf("%d", &b[i]);
}

void solve(unsigned int src[MAXN], unsigned int rez[MAXN], unsigned int sz)
{
    while (!q.empty()) q.pop();
    for (unsigned int i = 1; i <= sz; i++)
        q.push(cmp(src[i], i));
    for (unsigned int i = 1; i <= n; i++) {
        cmp top = q.top();
        q.pop();
        rez[i] = top.nr;
        q.push(cmp(top.nr + src[top.proc], top.proc));
    }
}

int main()
{
    freopen("fabrica.in", "r", stdin);
    freopen("fabrica.out", "w", stdout);

    read();
    solve(a, ba, nra);
    solve(b, bb, nrb);
    unsigned int sol = 0;
    printf("%d ", ba[n]);
    for (unsigned int i = 1; i <= n; i++)
        sol = max(sol, ba[i]+ bb[n-i+1]);
    printf("%d", sol);

    return 0;
}