Cod sursa(job #1690319)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 14 aprilie 2016 23:22:50
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#define pii pair<int,int>

using namespace std;

const int NM=100005;

priority_queue< pii, vector< pii >, greater< pii > > Heap;
int d[NM], a[NM], b[NM], i,n, A,B, Max=-1;
pair<int,int> Z;

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

    scanf("%d%d%d", &n, &A,&B);

    for(i=1; i<=A; ++i) scanf("%d", &a[i]);
    for(i=1; i<=B; ++i) scanf("%d", &b[i]);

    for(i=1; i<=A; ++i) Heap.push({a[i],i});

    for(i=1; i<=n; ++i)
    {
        Z=Heap.top();
        d[i]=Z.first;
        Heap.push({d[i]+a[Z.second], Z.second});
        Heap.pop();
    }
    printf("%d ", d[n]);

    while(Heap.size()) Heap.pop();

    for(i=1; i<=B; ++i) Heap.push({b[i],i});

    for(i=1; i<=n; ++i)
    {
        Z=Heap.top();
        d[n-i+1]+=Z.first;
        Heap.push({ d[i]+b[Z.second], Z.second});
        Heap.pop();

        if(d[n-i+1]>Max) Max=d[n-i+1];
    }

    printf("%d\n", Max);

    return 0;
}