Cod sursa(job #586102)

Utilizator diac_paulPaul Diac diac_paul Data 30 aprilie 2011 13:42:46
Problema Fabrica Scor 14
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Open Marime 1.75 kb
#include <stdio.h>
#define NMax 100005

FILE *fin = fopen("fabrica.in", "rt");
FILE *fout = fopen("fabrica.out", "wt");

int n, nra, nrb, oa[NMax], ob[NMax];
int a[NMax], b[NMax];

typedef struct doz
{
	int tip; // 0 - A, 1 - B
	int ind; // ind in a[] or b[]
	int ready; // ready time
}doz;

doz h[NMax];
int hs;

void insert(doz d);
doz getTop();
void intersch(int p1, int p2);
int main()
{
	fscanf(fin, "%d %d %d", &n, &nra, &nrb);

	for (int i = 0; i < nra; i++)
		fscanf(fin, "%d", &a[i]);
	for (int i = 0; i < nrb; i++)
		fscanf(fin, "%d", &b[i]);

	for (int i = 0; i < nra; i++)
	{
		doz d;
		d.tip = 0;
		d.ind = i;
		d.ready = a[i];
		insert(d);
	}

	for (int i = 0; i < n; i++)
	{
		doz d = getTop();
		oa[i] = d.ready;
		d.ready += a[d.ind];
		insert(d);
	}

	fprintf(fout, "%d ", oa[n-1]);

	hs = 0;
	for (int i = 0; i < nrb; i++)
	{
		doz d;
		d.tip = 1;
		d.ind = i;
		d.ready = b[i];
		insert(d);
	}

	for (int i = 0; i < n; i++)
	{
		doz d = getTop();
		ob[i] = d.ready + oa[0];
		d.ready += b[d.ind];
		insert(d);
	}

	fprintf(fout, "%d\n", ob[n - 1]);

	fclose(fin);
	fclose(fout);
	return 0;
}

void insert(doz d)
{
	h[hs] = d;

	int p = hs;
	while (h[p / 2].ready > h[p].ready)
	{
		intersch(p / 2, p);
		p /= 2;
	}

	hs++;
}

doz getTop()
{
	doz rez = h[0];
	int p = 0, p1, p2;

	h[0] = h[hs - 1];
	hs--;

	while (p < hs)
	{
		p1 = 2 * p + 1;
		p2 = 2 * p + 2;

		if (p2 < hs && h[p2].ready < h[p1].ready)
			p1 = p2;

		if (p1 >= hs)
			break;

		if (h[p].ready > h[p1].ready)
		{
			intersch(p, p1);
			p = p1;
		}
		else
		{
			break;
		}
	}

	return rez;
}

void intersch(int p1, int p2)
{
	doz aux = h[p1];
	h[p1] = h[p2];
	h[p2] = aux;
}