Cod sursa(job #585842)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 30 aprilie 2011 12:10:56
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Open Marime 1.25 kb
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define ff first
#define ss second
#define mp make_pair
#define pb push_back

typedef long long LL;

const int MMAX = 50005;
const int Inf = 2147483647;

int N, Na, Nb, a[MMAX], b[MMAX];

void read()
{
	ifstream fin("fabrica.in");
	fin>>N>>Na>>Nb;
	for (int i=0;i<Na;++i) fin>>a[i];
	for (int i=0;i<Nb;++i) fin>>b[i];
	fin.close();
}

priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > Q, W;
priority_queue< int, vector<int>, greater<int> > F;

void solve()
{
	int ta = 0, tb = 0;
	for (int i=0;i<Na;++i) Q.push(mp(a[i], a[i]));
	for (int i=0;i<Nb;++i) F.push(b[i]);
	for (int i=0;i<N;++i)
	{
		ta = Q.top().ff;
		int t = Q.top().ss;
		Q.pop();
		Q.push(mp(ta + t, t));
		
		int tt=Inf;
		if (!F.empty())
			tt=ta + F.top();

		if (!W.empty() && W.top().ff < tt)
		{
			tt = W.top().ff;
			t = W.top().ss;
			W.pop();
			W.push(mp(tt+t, t));
		}
		else
		{
			t = F.top();
			F.pop();
			W.push(mp(tt+t, t));
		}

		tb = max(tb, tt);
	}

	ofstream fout("fabrica.out");
	fout<<ta<<" "<<tb<<"\n";
	fout.close();
}

int main()
{
	read();
	solve();
	return 0;
}