Cod sursa(job #585734)

Utilizator cosmyoPaunel Cosmin cosmyo Data 30 aprilie 2011 11:31:12
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.3 kb
#include<cstdio>
#include<set>
using namespace std;
set<pair<int , int> > sa, sb;
const int N = 100005;
int n, nra, nrb, a[N], b[N], o[N], fina[N], finb[N];
struct tip{int val, a, b;};

tip x[N];
int main() {
	freopen("fabrica.in", "r", stdin);
	freopen("fabrica.out", "w", stdout);
	
	int i;
	scanf("%d %d %d", &n, &nra, &nrb);

	for(i = 1; i <= nra; ++i) {
		scanf("%d", &a[i]);
		sa.insert(make_pair(a[i], i));
	}

	for(i = 1; i <= nrb; ++i) {
		scanf("%d", &b[i]);
		sb.insert(make_pair(b[i], i));
	}
	
	set<pair<int, int> > :: iterator  it, is;
	int ind, val;
	for(i = 1; i <= n; ++i) {
		it = sa.begin();
		ind = (*it).second;
		val = (*it).first;
		x[i].val = val;
		x[i].a = ind;
		
		sa.erase(it);
		sa.insert(make_pair(val + a[ind], ind));
		
		it = sb.begin();
		ind = (*it).second;
		val = (*it).first;
		x[i].b = ind;

		sb.erase(it);
		sb.insert(make_pair(val + b[ind], ind));

	}

	for(i = 1; i <= n; ++i) {
		if(o[x[i].b] > x[i].val) {
			fina[i] = x[i].val;
			finb[i] = o[x[i].b] + b[x[i].b];
			o[x[i].b] += b[x[i].b];
		}

		else {
			fina[i] = x[i].val;
			finb[i] = x[i].val + b[x[i].b];
			o[x[i].b] = finb[i];
		}
	}

	int maxa = 0, maxb = 0;

	for(i = 1; i <= n; ++i){
		if(fina[i] > maxa)
			maxa = fina[i];

		if(finb[i] > maxb)
			maxb = finb[i];
	}

	printf("%d %d\n", maxa, maxb);

	return 0;
}