Pagini recente » Cod sursa (job #1779190) | Cod sursa (job #3004691) | Cod sursa (job #845243) | Cod sursa (job #89785) | Cod sursa (job #811778)
Cod sursa(job #811778)
#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;
}