Cod sursa(job #585616)

Utilizator MKLOLDragos Ristache MKLOL Data 30 aprilie 2011 10:20:35
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.55 kb
#include<stdio.h>
#include<algorithm>

#define Nmax 50050

int N,aint[4*Nmax];
int ind[4*Nmax],nra,nrb,x,min2;
int v[101010],a,b;
int s[101000];
int min1;
using namespace std;

void update(int nod,int poz,int val,int st,int dr)
{
    if(st==dr)
    {


        aint[nod]+=val;

        ind[nod]=poz;
    }
    else
    {
        int mij=(st+dr)/2;
        if(poz<=mij)
        update(2*nod,poz,val,st,mij);
        else
        update(2*nod+1,poz,val,mij+1,dr);
        if(aint[nod*2]>=aint[2*nod+1])
        {
            aint[nod]=aint[2*nod+1];
            ind[nod]=ind[2*nod+1];
        }
        else
        {
            aint[nod]=aint[2*nod];
            ind[nod]=ind[2*nod];
        }
    }
    return;
}
int main()
{
freopen("fabrica.in","r",stdin);
freopen("fabrica.out","w",stdout);
    scanf("%d%d%d",&N,&nra,&nrb);
    for(int i=1;i<=nra;++i)
    {

        scanf("%d",&s[i]);
        update(1,i,s[i],1,nra);
    }

    for(int i=1;i<=N;++i)
    {
        v[i]=aint[1];
        a=ind[1];
        b=s[a];
        update(1,a,b,1,nra);
    }
    for(int i=1;i<=N;++i)
    {
    min1=max(v[i],min1);
    }
    for(int i=1;i<=nra*4;++i)
    {
        aint[i]=0;
    }
    for(int i=1;i<=nrb;++i)
    {
    scanf("%d",&s[i]);
    update(1,i,s[i],1,nrb);
    }
    for(int i=N;i>=1;--i)
    {
        v[i]+=aint[1];
        a=ind[1];
        b=s[a];
        update(1,a,b,1,nrb);
    }
    for(int i=1;i<=N;++i)
    {
    min2=max(v[i],min2);
    }
    printf("%d %d\n",min1,min2);
return 0;
}