Cod sursa(job #586136)

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

#define DIM 100002

int a[DIM],b[DIM],t[3][DIM/2],n,nr1,nr2,sol,pas;


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

 void read ()
{
    int i;

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

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

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

    sort(1+a,1+a+n);
    for(i=1;i<=n;++i)
    {
        nr=h.top();
        h.pop ();
        a[i]+=max(b[nr]-a[i],0)+t[pas][nr];
        b[nr]=a[i];
        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;
}