Cod sursa(job #2311804)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 3 ianuarie 2019 18:25:23
Problema Fabrica Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin ("fabrica.in");
ofstream cout ("fabrica.out");
long long heap[50003],elemx,rez1[50003],rez2[50003],v[50003],vv[50003];
void baga(long long val)
{
    heap[++elemx]=val;
    long long poz=elemx;
    while(poz>1 && v[heap[poz]]<v[heap[poz/2]])
    {
        swap(heap[poz],heap[poz/2]);
        poz>>=1;
    }
}
void scoate ()
{
    long long poz=1;
    swap(heap[1],heap[elemx]);
    --elemx;
    while(poz*2+1<=elemx && v[heap[poz]]>min(v[heap[poz*2]],v[heap[poz*2+1]]))
    {
        if(v[heap[poz*2]]<v[heap[poz*2+1]])
        {
            swap(heap[poz*2],heap[poz]);
            poz<<=1;
        }
        else
        {
            swap(heap[poz*2+1],heap[poz]);
            poz<<=1;
            ++poz;
        }
    }
    if(poz*2==elemx && v[heap[poz]]>v[heap[poz*2]])
        swap(heap[poz],heap[poz*2]);
}
int main()
{
    long long m,mm,n,a,b,i,mx=-1;
    cin>>n>>m>>mm;
    for(i=1;i<=m;++i)
    {
        cin>>vv[i];
        v[i]=vv[i];
        baga(i);
    }
    for(i=1;i<=n;++i)
    {
        rez1[i]=v[heap[1]];
        v[heap[1]]+=vv[heap[1]];
        a=heap[1];
        scoate();
        baga(a);
    }
    elemx=0;
    cout<<rez1[n]<<' ';
    for(i=1;i<=mm;++i)
    {
        cin>>vv[i];
        v[i]=vv[i];
        baga(i);
    }
    for(i=1;i<=n;++i)
    {
        rez2[i]=v[heap[1]];
        v[heap[1]]+=vv[heap[1]];
        a=heap[1];
        scoate();
        baga(a);
    }
    for(i=1;i<=n;++i)
        mx=max(mx,rez1[i]+rez2[n-i+1]);
    cout<<mx;
}