Cod sursa(job #585623)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 30 aprilie 2011 10:24:11
Problema Fabrica Scor 6
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.35 kb
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>
#define LMAX 50005
#define NMAX 100005
#define ll long long
#define pii pair <int,int>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
int n,m,val,A[LMAX],B[LMAX],rez1;
set <pii> S;
int C[NMAX],r;
pii D[NMAX];
void read()
{
	scanf("%d%d%d",&val,&n,&m);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
	for (i=1; i<=m; i++)
		scanf("%d",&B[i]);
}
void search()
{
	int i,poz;
	for (i=1; i<=n; i++)
		S.insert(mp(A[i],i));
	for (i=1; i<=val; i++)
	{
		rez1=(*S.begin()).f; poz=(*S.begin()).s;
		C[i]=rez1;
		S.erase(S.begin());
		S.insert(mp(rez1+A[poz],poz));
	}
}
inline int ok(int x)
{
	int i,v,poz,value;
	S.clear();
	set <pii> :: iterator it;
	for (i=1; i<=m; i++)
		D[i]=mp(B[i],i);
	int j;
	for (i=1; i<=val; i++)
	{
		poz=0;
		for (j=1; j<=m; j++)
			if (D[j].f<=x-C[i])
				poz=i;
		if (poz==0)
			return 0;
		D[poz].f+=B[D[poz].s];
		sort(D+1,D+m+1);
	}
	return 1;
}
inline int cb()
{
	int i,step=(1<<30);
	for (i=0; step; step>>=1)
		if (!ok(i+step))
			i+=step;
	return ++i;
}
int main()
{
	freopen("fabrica.in","r",stdin);
	freopen("fabrica.out","w",stdout);
	read();
	sort(A+1,A+n+1);
	sort(B+1,B+m+1);
	search();
	printf("%d ",rez1);
	printf("%d\n",cb());
	return 0;
}