Cod sursa(job #589274)

Utilizator AndreyPAndrei Poenaru AndreyP Data 11 mai 2011 18:31:58
Problema Fabrica Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <functional>
#include <algorithm>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define ui unsigned int
#define puu pair< ui,ui >
#define N 100010

int n,nra,nrb;
puu h[N];
ui a[N],b[N];
ui rez;

inline void citire(int n) {
	puu x;
	for(int i=1; i<=n; ++i) {
		scanf("%u",&x.fs);
		x.sc = x.fs;
		h[i] = x;
	}
}

inline void rezolva(int n1,ui a[N]) {
	puu aux;
	make_heap(h+1,h+n1+1,greater< puu >());
	for(int i=1; i<=n; ++i) {
		aux = h[1];
		pop_heap(h+1,h+n1+1,greater< puu >());
		a[i] = aux.fs;

		aux.fs += aux.sc;
		h[n1] = aux;
		push_heap(h+1,h+n1+1,greater< puu >());
	}
}

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

	scanf("%d%d%d",&n,&nra,&nrb);
	citire(nra);
	rezolva(nra,a);
	citire(nrb);
	rezolva(nrb,b);

	rez = a[1]+b[n];
	ui aux;
	for(int i=2; i<=n; ++i) {
		aux = a[i]+b[n-i+1];
		if(aux>rez)
			rez = aux;
	}

	printf("%u %u\n",a[n],rez);
	return 0;
}