Cod sursa(job #585863)

Utilizator maritimCristian Lambru maritim Data 30 aprilie 2011 12:19:19
Problema Fabrica Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 5-9 Marime 1.03 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

#define INF 1000000

int A[50001];
int B[50001];
int N;
int a;
int b;
int nr;
int MAX = -INF;

void swap(int a,int b)
{
	int c = A[a];
	A[a] = A[b];
	A[b] = c;
	c = B[a];
	B[a] = B[b];
	B[b] = c;
}

void sorti(void)
{
	for(int i=2;B[i] && A[i]*B[i]<=A[i-1]*B[i-1];i++)
		swap(i,i-1);
}

void solve(void)
{
	memset(B,0,sizeof(B));
	nr += A[2]/A[1];
	if(A[2]%A[1])
		nr ++;
	B[1] = nr;
	swap(1,2);
	for(;nr<N;)
	{
		int x = (A[2]*B[2]-A[1]*B[1])/A[1];
		int y = (A[2]*B[2]-A[1]*B[1])%A[1];
		if(y)
			x ++;
		if(!x)
			x = 1;
		nr += x;
		B[1] += x;
		sorti();
	}
	if(nr>N)
		B[1] -= N-nr;
	for(int i=1;i<=a;i++)
		if(MAX<B[i]*A[i])
			MAX = B[i]*A[i];
}

int main()
{
	FILE *f = fopen("fabrica.in","r");
	FILE *g = fopen("fabrica.out","w");
	
	fscanf(f,"%d %d %d",&N,&a,&b);
	for(int i=1;i<=a;i++)
		fscanf(f,"%d",&A[i]);
	sort(A+1,A+a+1);
	solve();
	fprintf(g,"%d",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}