Cod sursa(job #585453)

Utilizator devilkindSavin Tiberiu devilkind Data 29 aprilie 2011 15:24:44
Problema Fabrica Scor Ascuns
Compilator cpp Status done
Runda Marime 1.42 kb
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define ii pair<int, int>
#define mp make_pair

const int lg = 100002;

int n, m1, m2, timp[lg], last[lg], tmp1, tmp2, a[lg], b[lg], i, pz, next[lg], j;
ii rez;

bool ok(int s, int val){
	int i, vf, ind = 0;
	
	if (!s){
		for (i = 1; i <= m1; i ++)
			ind += val / a[i];

		if (ind >= n)
			return 1;
		return 0;
	}


	priority_queue<ii, vector<ii> > hp;

	for (i = 1; i <= m2; i ++)
		hp.push(mp(val - b[i], i));

	for (vf = n, i = 1; i <= n; i ++, vf --){
		rez = hp.top(); hp.pop();

		if (timp[vf] > rez.x)
			return 0;

		hp.push(mp(rez.x - b[ rez.y ], rez.y));
	}

	return 1;

}

int bs(int s){
	int li = 1, ls = 1000000000, x, gs = -1;

	while (li <= ls){
		x = (li + ls) / 2;

		if (ok(s, x) == 1){
			gs = x;
			ls = x - 1;
		}
		else
			li = x + 1;
	}

	return gs;
}

int main()
{
	freopen("fabrica.in", "rt", stdin);
	freopen("fabrica.out", "wt", stdout);

	scanf("%d%d%d", &n, &m1, &m2);
	for (i = 1; i <= m1; i ++)
		scanf("%d", &a[i]);
	for (i = 1; i <= m2; i ++)
		scanf("%d", &b[i]);

	tmp1 = bs(0);

	priority_queue<ii, vector<ii> > hp;
	for (i = 1; i <= m1; i ++)
		hp.push(mp(-a[i], i));
	for (i = 1; i <= n; i ++){
		rez = hp.top(); hp.pop();
			
		timp[i] = -rez.x;

		hp.push(mp(rez.x - a[ rez.y ], rez.y));
	}

	sort(timp + 1, timp + n + 1);

	tmp2 = bs(1);

	printf("%d %d\n", tmp1, tmp2);

	return 0;
}