Cod sursa(job #585789)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 30 aprilie 2011 11:52:32
Problema Fabrica Scor 4
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.93 kb
#include <stdio.h>
#include <algorithm>
#include <set>

using namespace std;

#define maxn 200010

int n, i, j, k, nra, nrb, tc, mc, left, med, right, sa, sb;
long long nc;
int a[maxn], b[maxn];
int ap[maxn];
set<pair<int, int> > g, disp;

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", &a[i]);
    for(int i=1; i<=nrb; ++i)
        scanf("%d", &b[i]);

    left=0;
    right=2000000000;
    while(left<=right)
    {
        med=(1LL*left+right)/2;
        nc=0;
        for(int i=1; i<=nra; ++i)
        {
            nc=nc+med/a[i];
            if(nc>=n)
                break;
        }
        if(nc>=n)
        {
            sa=med;
            right=med-1;
        }
        else
            left=med+1;
    }

    printf("%d ", sa);

    for(int i=1; i<=nra; ++i)
        for(int j=a[i]; j<=sa; ++j)
            ap[++ap[0]]=j;

    for(int i=1; i<=nrb; ++i)
        disp.insert(make_pair(b[i], i));

    left=0;
    right=2000000000;

    sort(ap+1, ap+ap[0]+1);

    while(left<=right)
    {
        med=(1LL*left+right)/2;
        for(int i=1; i<=n; ++i)
            g.insert(make_pair(ap[i], 0));

        mc=0;
        while(g.size()>0)
        {
            if(g.begin()->first>med)
                break;
            if(g.begin()->second==0)
                ++mc;
            else
                disp.insert(make_pair(b[g.begin()->second], g.begin()->second));

            tc=g.begin()->first;
            g.erase(g.begin());
            while(mc>0 && disp.size()>0)
            {
                --mc;
                g.insert(make_pair(tc+(disp.begin()->first), disp.begin()->second));
                disp.erase(disp.begin());
            }
        }
        if(g.size()==0)
        {
            sb=med;
            right=med-1;
        }
        else
            left=med+1;
    }
    printf("%d\n", sb);
    return 0;
}