Cod sursa(job #120122)

Utilizator andrei.12Andrei Parvu andrei.12 Data 4 ianuarie 2008 12:08:11
Problema Economie Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<algorithm>
#define lg1 1005
#define lg2 50005

using namespace std;

int n, i, j, v[lg1], q[lg2], mx, d[lg2], x, fst[lg2], sol[lg1], rht[lg1];
int main()
{
	freopen("economie.in", "rt", stdin);
	freopen("economie.out", "wt", stdout);
	
	scanf("%d", &n);
	
	for (i = 1; i <= n; i ++){
		scanf("%d", &v[i]);
		q[v[i]] = 1;
		mx = max(mx, v[i]);
	}
	
	sort(v+1, v+n+1);
	d[0] = 1;
	for (i = 1; i <= n; i ++)
		for (j = 0; j <= mx; j ++)
			if (d[j]){
				x = j + v[i];
				if (x <= mx){
					d[x] = 1;
					if (q[x] == 1 && !fst[x]){
						if (!rht[i])
							sol[++sol[0]] = v[i], rht[i] = 1;
						fst[x] = 1;
					}
				}
			}
	
	printf("%d\n", sol[0]);
	for (i = 1; i <= sol[0]; i ++)
		printf("%d\n", sol[i]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}