Cod sursa(job #586000)

Utilizator DraStiKDragos Oprica DraStiK Data 30 aprilie 2011 13:09:31
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 3.38 kb
#include <algorithm>
#include <cstdio>
using namespace std;

#define DIM 50005

int aint_minA[DIM<<2],aint_pozA[DIM<<2],aint_minB[DIM<<2],aint_pozB[DIM<<2];
int vA[DIM],vB[DIM],tmpA[DIM<<1],tmpB[DIM<<1];
int N,NA,NB,sol;

void read ()
{
    int i;

    scanf ("%d%d%d",&N,&NA,&NB);
    for (i=1; i<=NA; ++i)
        scanf ("%d",&vA[i]);
    for (i=1; i<=NB; ++i)
        scanf ("%d",&vB[i]);
}

void buildA (int nod,int st,int dr)
{
    int mij;

    if (st==dr)
    {
        aint_pozA[nod]=st;
        return ;
    }

    mij=(st+dr)>>1;
    buildA (nod<<1,st,mij);
    buildA ((nod<<1)|1,mij+1,dr);

    if (aint_minA[nod<<1]+vA[aint_pozA[nod<<1]]<aint_minA[(nod<<1)|1]+vA[aint_pozA[(nod<<1)|1]])
    {
        aint_minA[nod]=aint_minA[nod<<1];
        aint_pozA[nod]=aint_pozA[nod<<1];
    }
    else
    {
        aint_minA[nod]=aint_minA[(nod<<1)|1];
        aint_pozA[nod]=aint_pozA[(nod<<1)|1];
    }
}

void updateA (int nod,int st,int dr,int poz,int val)
{
    int mij;

    if (st==dr)
    {
        aint_minA[nod]+=val;
        return ;
    }

    mij=(st+dr)>>1;

    if (poz<=mij)
        updateA (nod<<1,st,mij,poz,val);
    else
        updateA ((nod<<1)|1,mij+1,dr,poz,val);

    if (aint_minA[nod<<1]+vA[aint_pozA[nod<<1]]<aint_minA[(nod<<1)|1]+vA[aint_pozA[(nod<<1)|1]])
    {
        aint_minA[nod]=aint_minA[nod<<1];
        aint_pozA[nod]=aint_pozA[nod<<1];
    }
    else
    {
        aint_minA[nod]=aint_minA[(nod<<1)|1];
        aint_pozA[nod]=aint_pozA[(nod<<1)|1];
    }
}

void buildB (int nod,int st,int dr)
{
    int mij;

    if (st==dr)
    {
        aint_pozB[nod]=st;
        return ;
    }

    mij=(st+dr)>>1;
    buildB (nod<<1,st,mij);
    buildB ((nod<<1)|1,mij+1,dr);

    aint_minB[nod]=aint_minB[nod<<1];
    aint_pozB[nod]=aint_pozB[nod<<1];

    if (aint_minB[nod<<1]+vB[aint_pozB[nod<<1]]<aint_minB[(nod<<1)|1]+vB[aint_pozB[(nod<<1)|1]])
    {
        aint_minB[nod]=aint_minB[nod<<1];
        aint_pozB[nod]=aint_pozB[nod<<1];
    }
    else
    {
        aint_minB[nod]=aint_minB[(nod<<1)|1];
        aint_pozB[nod]=aint_pozB[(nod<<1)|1];
    }
}

void updateB (int nod,int st,int dr,int poz,int val)
{
    int mij;

    if (st==dr)
    {
        aint_minB[nod]+=val;
        return ;
    }

    mij=(st+dr)>>1;

    if (poz<=mij)
        updateB (nod<<1,st,mij,poz,val);
    else
        updateB ((nod<<1)|1,mij+1,dr,poz,val);

    if (aint_minB[nod<<1]+vB[aint_pozB[nod<<1]]<aint_minB[(nod<<1)|1]+vB[aint_pozB[(nod<<1)|1]])
    {
        aint_minB[nod]=aint_minB[nod<<1];
        aint_pozB[nod]=aint_pozB[nod<<1];
    }
    else
    {
        aint_minB[nod]=aint_minB[(nod<<1)|1];
        aint_pozB[nod]=aint_pozB[(nod<<1)|1];
    }
}

void solve ()
{
    int i,poz;

    buildA (1,1,NA);
    for (i=1; i<=N; ++i)
    {
        poz=aint_pozA[1];
        tmpA[i]=aint_minA[1]+vA[poz];
        updateA (1,1,NA,poz,vA[poz]);
    }
    sort (tmpA+1,tmpA+N+1);

    buildB (1,1,NB);
    for (i=1; i<=N; ++i)
    {
        poz=aint_pozB[1];
        tmpB[i]=max (tmpA[i],aint_minB[1])+vB[poz];
        updateB (1,1,NB,poz,vB[poz]);
    }
    sort (tmpB+1,tmpB+N+1);

    printf ("%d %d",tmpA[N],tmpB[N]);
}

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

    read ();
    solve ();

    return 0;
}