Cod sursa(job #109637)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 25 noiembrie 2007 12:14:46
Problema Economie Scor 100
Compilator cpp Status done
Runda preONI 2008, Runda 1, Clasa a 10-a Marime 0.69 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 1024
#define MAXV 50005

int N, x[MAXN];
char in[MAXN];

char pos[MAXV];

int main()
{
	freopen("economie.in", "rt", stdin);
	freopen("economie.out", "wt", stdout);

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", x + i), in[i] = 1;
	sort(x, x + N);
	
	int NR = 0; pos[0] = 1;
	for (int i = 0; i < N; i++)
	{
		if (!in[i]) continue;
		NR++;
		for (int j = 0; j + x[i] < MAXV; j++)
		{
			if (!pos[j]) continue;
			pos[ j + x[i] ] = 1;
		}

		for (int j = i + 1; j < N; j++)
			if (in[j] && pos[ x[j] ])
				in[j] = 0;
	}
	printf("%d\n", NR);
	for (int i = 0; i < N; i++)
		if (in[i])
			printf("%d\n", x[i]);

	return 0;
}