Cod sursa(job #585674)

Utilizator darrenRares Buhai darren Data 30 aprilie 2011 10:56:22
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N, Na, Nb;
int T1[100002], T2[100002];
long long Ta, Tb;
long long Cons1[100002], Cons2[100002], Times[100002];

class compare1
{
    public: bool operator () (const int& i1, const int& i2)
    {
        return Cons1[i1] + T1[i1] > Cons1[i2] + T1[i2];
    }
};
class compare2
{
    public: bool operator () (const int& i1, const int& i2)
    {
        return Cons2[i1] + T2[i1] > Cons2[i2] + T2[i2];
    }
};
priority_queue<int, vector<int>, compare1> P1;
priority_queue<int, vector<int>, compare2> P2;

int main()
{
    ifstream fin("fabrica.in");
    ofstream fout("fabrica.out");

    fin >> N >> Na >> Nb;
    for (int i = 1; i <= Na; ++i)
        fin >> T1[i];
    for (int i = 1; i <= Nb; ++i)
        fin >> T2[i];

    for (int i = 1; i <= Na; ++i)
        P1.push(i);
    for (int i = 1; i <= N; ++i)
    {
        int aux = P1.top(); P1.pop();
        Times[i] = Cons1[aux] + T1[aux];
        Cons1[aux] += T1[aux];
        P1.push(aux);

        Ta = max(Ta, Cons1[aux]);
    }

    // sort(Times + 1, Times + N + 1);

    for (int i = 1; i <= Nb; ++i)
        P2.push(i);
    for (int i = 1; i <= N; ++i)
    {
        int aux = P2.top(); P2.pop();
        Cons2[aux] = max(Times[i], Cons2[aux]) + T2[aux];
        P2.push(aux);

        Tb = max(Tb, Cons2[aux]);
    }

    fout << Ta << ' ' << Tb;

    fin.close();
    fout.close();
}