Cod sursa(job #586111)

Utilizator ProtomanAndrei Purice Protoman Data 30 aprilie 2011 13:44:12
Problema Fabrica Scor 16
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.26 kb
#include <algorithm>
#include <stdio.h>
#include <set>

#define MAX 100010
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, nra, nrb;
multiset <int> setDur;
multiset <pair <int, int> > setMom, setDis;
int vctIn[MAX];

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

	scanf("%d %d %d", &n, &nra, &nrb);

	for (int i = 1; i <= nra; i++)
	{
		int dur;
		scanf("%d", &dur);
		setMom.insert(mp(0, dur));
	}

	for (int i = 1; i <= nrb; i++)
	{
		int dur;
		scanf("%d", &dur);
		setDur.insert(dur);
	}

	for (; vctIn[0] < n; )
	{
		int mom = setMom.begin()->f;
		int dur = setMom.begin()->s;

		setMom.erase(setMom.begin());

		if (mom != 0)
			vctIn[++vctIn[0]] = mom;
		setMom.insert(mp(mom + dur, dur));
	}

	int m1 = vctIn[n], m2 = 0;

	for (int i = n; i; i--)
	{
		for (; setDis.begin() != setDis.end(); setDis.erase(setDis.begin()))
			if (setDis.begin()->f <= -vctIn[i])
				setDur.insert(setDis.begin()->s);
			else break;

		int dur = (*setDur.begin());
		setDur.erase(setDur.begin());

		m2 = max(m2, vctIn[i] + dur);

		setDis.insert(mp(-(vctIn[i] - dur), dur));
	}

	printf("%d %d\n", m1, m2);

	fclose(stdin);
	fclose(stdout);
	return 0;
}