Cod sursa(job #789281)

Utilizator tester9x9Tester9x9 tester9x9 Data 17 septembrie 2012 18:51:06
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <queue>
#define NM 100010

using namespace std;

ifstream f("fabrica.in");
ofstream g("fabrica.out");

int N,NA,NB,i,j;
int X;
int ANS[NM];
int ANS1;
int C,T;

typedef pair<int,int> PI;

struct QueCMP
{
    bool operator () (const PI& a, const PI& b) const
    {
        return (a.first+a.second)>(b.first+b.second);
    }
};

priority_queue<PI, vector<PI>, QueCMP > Q;

int main ()
{
    f >> N >> NA >> NB;
    for (i=1; i<=NA; i++)
    {
        f >> X;
        Q.push(make_pair(X,0));
    }
    for (i=1; i<=N; i++)
    {
        C=Q.top().first;
        T=Q.top().second;
        Q.pop();
        ANS[i]=T+C;
        Q.push(make_pair(C,ANS[i]));
        ANS1=max(ANS1,ANS[i]);
    }
    g << ANS1 << ' ';

    ANS1=0;
    sort(ANS+1,ANS+N+1);

    while (!Q.empty()) Q.pop();

    for (i=1; i<=NB; i++)
    {
        f >> X;
        Q.push(make_pair(X,0));
    }

    for (i=N; i>=1; i--)
    {
        C=Q.top().first;
        T=Q.top().second;
        Q.pop();
        if (ANS[i]>T) T=ANS[i];
        T+=C;
        ANS1=max(ANS1,T);
        Q.push(make_pair(C,T));
    }

    g << ANS1 << '\n';


    f.close();
    g.close();
    return 0;
}