Cod sursa(job #586022)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 30 aprilie 2011 13:19:59
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.24 kb
#include<algorithm>
#include<cstdio>
using namespace std;
#include<vector>
#include<queue>

#define DIM 100002

int a[DIM],b[DIM],t1[DIM/2],t2[DIM/2],n,nr1,nr2,sol;


struct cmp
{
    bool operator ()(const int &x,const int &y)const
    {
        return b[x]>b[y];
    }
}; priority_queue<int,vector<int>,cmp> h;

 void read ()
{
    int i;

    scanf("%d%d%d",&n,&nr1,&nr2);
    for(i=1;i<=nr1;++i)
    {
        scanf("%d",&t1[i]);
        h.push(i);
    }
    for(i=1;i<=nr2;++i)
        scanf("%d",&t2[i]);
}

void solve ()
{
    int i,nr;

    for(i=1;i<=n;++i)
    {
        nr=h.top();
        h.pop ();
        a[i]=b[nr]+t1[nr];
        b[nr]=a[nr];
        h.push(nr);
        sol=max(sol,a[i]);
    }
    printf("%d ",sol);

    sol=0;
    while(!h.empty())
        h.pop ();
    for(i=1;i<=nr2;++i)
    {
        b[i]=0;
        h.push (i);
    }

    for(i=1;i<=n;++i)
    {
        nr=h.top();
        h.pop ();
        a[i]=max(a[i],b[nr])+t2[nr];
        b[nr]=a[nr];
        h.push(nr);
        sol=max(sol,a[i]);
    }
    printf("%d\n",sol);
}

int main ()
{
    freopen("fabrica.in","r",stdin);
    freopen("fabrica.out","w",stdout);
    read ();
    solve ();
    return 0;
}