Cod sursa(job #586716)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 2 mai 2011 20:15:25
Problema Fabrica Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string>
#include <cstring>

#define MAXN 100005
using namespace std;

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

struct Point {
	int x, y;
	bool operator < (const Point &o) const {
		return x + A[y] > o.x + A[o.y];
	}
};

priority_queue <Point> Q1;
Point nod;
int mx, i, add;
vector <int> T, V;
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]);
	}
	

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

		nod.x += A[nod.y];
		mx = max (mx, nod.x);
		T.push_back (nod.x);
		Q1.push (nod);
	}

	int ls, ld, mid, l, sol = 0;

	sort (T.begin (), T.end ());

	ls = 1; ld = 1 << 29;
		
	while (ls <= ld) {
		mid = (ls + ld) >> 1;
		
	//	printf ("%d %d %d\n", ls, mid, ld);
		
		memset (vB, 0, sizeof (vB));
		V = T;
		int n = N - 1;

		for (l = nrB; l >= 2 && n >= 0; l--) {
			while (1) 
			{
				if (n == -1) break;

				int left, right, med, val;
				left = 0; right = n;
				
				int SS = -1;
				
				while (left <= right) {
					med = (left + right) >> 1;
					val = max (V[med], vB[l]) + B[l];
					
					if (val > mid) 
						right = med - 1;
					else {
						left = med + 1;
						SS = med;
					}
				}
				if (SS != -1) {
					vB[l] = max (V[SS], vB[l]) + B[l];
					V.erase (V.begin () + SS);
					n -= 1;
				/*	if (mid == 10) {
						for (int j = 0; j < V.size (); j++)
							printf ("%d ", V[j]);
						printf ("\n");
					}
				*/}
				else break;
			}
			//printf ("%d ", vB[l]);
		}
		for (int j = 0; j <= n; j++)
			vB[l] = max (vB[l], V[j]) + B[l];
		if (vB[l] <= mid) {
			sol = mid;
			ld = mid - 1;
		}
		else ls = mid + 1;
	}

	printf ("%d %d\n", T[N - 1], sol);
	return 0;
}