Cod sursa(job #811778)

Utilizator vendettaSalajan Razvan vendetta Data 12 noiembrie 2012 22:06:17
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 100005
#define ll long long

int n, nrA, nrB, rezA[nmax], rezB[nmax], a[nmax], b[nmax];
multiset< pair<int,int> > S;

void citeste(){

	f >> n >> nrA >> nrB;
    for(int i=1; i<=nrA; ++i) f >> a[i];
    for(int i=1; i<=nrB; ++i) f >> b[i];

}

void rezolva(){

    //idea ar fi in felul urmator : cele 2 procese sunt independente doar cu precizarea ca o bere trece intai prin procesul A
    //iar apoi prin procesul B
    //deci imi calculez pentru fiecare bere cat de rapid se termina la fiecare din cele 2 procesoare
    // avand aceste valori calculate o sa am ceva de genul : rezA[i] = timpul la care se termin a i-a bere in primul proces
    //respectiv rezB[i] = timpyl la care se termina a i-a bere in al 2 lea proces;
    //pt prima cerinta clar e maximul din A; pt a 2 -a urmeaza partea mai interesanta;
    // am doi vectori care sunt ambii sortati crescator cerinta a 2 mai poate fi "transformata" in : trebuie sa gasesc o modalitate
    // de asociere intre cei doi vectori a. i. sa fac N perechi; raspunsul va fi maximul sumei dintre cei 2 termini ai fiecarei perechi
    // cel mai optim ar fi ca primul sa il iau cu cel mai tarziu al 2 lea cu al n-1 lea cel mai tarziu; pt ca astfel suma maxima posibila
    //va fi tot timpul si cea mai mica posibila

    for(int i=1; i<=nrA; ++i)
        S.insert( make_pair(a[i], a[i]) );

    for(int i=1; i<=n; ++i){
        int la_cat = (*S.begin()).first;//la cat se termina a i-a bere
        int cu_cat = (*S.begin()).second;// si cat dureaza procesul
        S.erase(S.begin());
        rezA[i] = la_cat;
        S.insert( make_pair( la_cat+cu_cat, cu_cat ) );//bag la cat o sa se termine o bere din viitor
    }

    S.clear();//il golesc si fac pt a 2lea proces;
    for(int i=1; i<=nrB; ++i)
        S.insert( make_pair(b[i], b[i]) );

    for(int i=1; i<=n; ++i){
        int la_cat = (*S.begin()).first;
        int cu_cat = (*S.begin()).second;
        S.erase(S.begin());
        rezB[i] = la_cat;
        S.insert( make_pair( la_cat + cu_cat, cu_cat) );
    }

    //rezolv cerintele
    int rez1 = 0; int rez2 = 0;
    for(int i=1,j=n; i<=n; ++i,--j){
        rez1 = max(rez1, rezA[i]);
        rez2 = max(rez2, rezA[i]+rezB[j]);
    }

    cout << rez1 << " " << rez2 << "\n";
    g << rez1 << " " << rez2 << "\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}