Cod sursa(job #585975)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 30 aprilie 2011 13:02:47
Problema Fabrica Scor 20
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.25 kb
#include <cstdio>
#include <queue>
#include <algorithm>

#define MAXN 100005
using namespace std;

int A[MAXN], B[MAXN], N, nrA, nrB;

struct Point {
	int x, y;
	bool operator < (const Point &o) const {
		return x + A[y] > o.x + A[o.y];
	}
};
struct Point2 {
	int x, y;
	bool operator < (const Point2 &o) const {
		return x + B[y] > o.x + B[o.y];
	}
};
priority_queue <Point> Q1;
priority_queue <Point2> Q2;
Point nod; Point2 nod2;
int mx, i, T[MAXN], add;
int main ()
{


	freopen ("fabrica.in", "r", stdin);
	freopen ("fabrica.out", "w", stdout);


	scanf ("%d %d %d\n", &N, &nrA, &nrB);

	for (i = 1; i <= nrA; i++) {		
		scanf ("%d\n", &A[i]);
		nod.x = 0; nod.y = i;
		Q1.push (nod);
	}

	for (i = 1; i <= nrB; i++) {
		scanf ("%d\n", &B[i]);
		nod2.x = B[i]; nod2.y = i;
		Q2.push (nod2);
	}
	

	for (i = 1; i <= N; i++) {
		nod = Q1.top ();
		Q1.pop ();

		nod.x += A[nod.y];
		mx = max (mx, nod.x);
		T[i] = nod.x;
		Q1.push (nod);
	}
	printf ("%d ", mx);

	mx = 0;
	sort (T + 1, T + N + 1);	
	for (i = 1; i <= N; i++) {
		nod2 = Q2.top ();
		Q2.pop ();
		add = 0;
		if (T[i] > nod2.x) add = T[i] - nod2.x;
		nod2.x += B[nod2.y] + add;
		
		Q2.push (nod2);
		mx = max (nod2.x, mx);
//		printf ("%d %d %d\n", T[i], nod2.x, nod2.y);
	}
	printf ("%d\n", mx);
	return 0;
}