Cod sursa(job #586137)

Utilizator cosmyoPaunel Cosmin cosmyo Data 30 aprilie 2011 13:49:32
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.42 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], p1, p2;
struct tip{int val, ind, o;};

tip x[N];

tip v[N * 4];

void update(int k, int st, int dr, int poz) {
	if(dr < 1 || st > nrb)
		return ;
	
	if(1 <= st && dr <= nrb) {
		if(v[poz].val - b[v[poz].ind] < k) 
			v[poz].val = k + b[v[poz].ind], v[poz].o = k;
		return ;
	}
	
	int x = (st + dr) / 2;
	update(k, st, x, poz * 2);
	update(k, x + 1, dr, poz * 2 + 1);
	if(v[poz * 2].val < v[poz * 2 + 1].val)
		v[poz] = v[poz * 2];
	else
		v[poz] = v[poz * 2 + 1];
}

void update2(int val, int st, int dr, int poz) {
	if(dr < p1 || st > p2)
		return ;


	if(v[poz].o == 1) {
		if(v[poz * 2].val - b[v[poz * 2].ind] < v[poz].o)
			v[poz * 2].val = v[poz].o + b[v[poz * 2].ind];

		if(v[poz * 2 + 1].val - b[v[poz * 2 + 1].ind] < v[poz].o)
			v[poz * 2 + 1].val = v[poz].o + b[v[poz * 2].ind];
		
		v[poz * 2].o = v[poz * 2 + 1].o  = v[poz].o;
		v[poz].o = 0;
	}
	
	if(p1 <= st && dr <= p2) {
		v[poz].val = val;
		v[poz].ind = p1;
		v[poz].o = 0;
		return ;
	}

	int x = (st + dr) / 2;

	update2(val, st, x, poz * 2);
	update2(val, x + 1, dr, poz * 2 + 1);

	if(v[poz * 2].val < v[poz * 2 + 1].val)
		v[poz] = v[poz * 2];
	else
		v[poz] = v[poz * 2 + 1];
}

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].ind = ind;
		
		sa.erase(it);
		sa.insert(make_pair(val + a[ind], ind));
		
	}

	
	int maxa = 0, maxb = 0;
	for(i = 1; i <= nrb; ++i){
		p1 = i;
		p2 = i;
		update2(b[i], 1, nrb, 1);
	}
	
//	for(i = 1; i <= n * 2; ++i)
//		printf("%d %d\n", v[i].val, v[i].ind);

	for(i = 1; i <= n; ++i){
		update(x[i].val, 1, nrb, 1);
		int p = v[1].ind;
//		printf("%d %d\n", p, v[1].val);	
		if(maxb < v[1].val)
			maxb = v[1].val;
	
		if(maxa < x[i].val)
			maxa = x[i].val;
		p1 = p;
		p2 = p;

		update2(x[i].val + b[p], 1, nrb, 1);
//		printf("\n");
//		for(int poz = 1; poz <= 3; ++poz)
//			printf("%d %d\n", v[poz].val, v[poz].ind);
//		printf("\n");
	}

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

	return 0;
}