Cod sursa(job #109437)

Utilizator tvladTataranu Vlad tvlad Data 25 noiembrie 2007 11:05:46
Problema Economie Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 1, Clasa a 9-a Marime 1.4 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1000;
const int VM = 5000;

struct elem { int v; elem *next, *prev; };

int nv,n;
int v[N],a[N];
elem *wh[VM+1];

elem *init ( int x ) {
	elem *a = new elem;
	(*a).v = x;
	(*a).prev = (*a).next = NULL;
	return a;
}

elem *push ( int x, elem *wh ) {
	elem *a = new elem;
	(*a).v = x;
	(*a).prev = wh;
	(*a).next = NULL;
	(*wh).next = a;
	return a;
}
elem *pop ( elem* who ) {
	if ((*who).prev != NULL) (*(*who).prev).next = (*who).next;
	if ((*who).next != NULL) (*(*who).next).prev = (*who).prev;
	elem *a = (*who).next;
	wh[(*who).v] = NULL;
	delete who;
	return a;
}

int main() {
	freopen("economie.in","rt",stdin);
	freopen("economie.out","wt",stdout);
	scanf("%d",&nv);
	int max = 0;
	for (int i = 0; i < nv; ++i) {
		scanf("%d",&v[i]);
		if (max < v[i]) max = v[i];
	}

	sort(v,v+nv);
	n = 0; a[0] = v[0];
	for (int i = 1; i < nv-1; ++i)
		if (a[n] != v[i]) a[++n] = v[i];

	wh[0] = NULL;
	elem *start = init(0);
	wh[1] = push(1,start);
	for (int i = 2; i <= max; ++i) wh[i] = push(i,wh[i-1]);
	vector<int> s;
	for (int i = 0; i < n; ++i) {
		if (wh[a[i]]) {
			s.push_back(a[i]);
			for(elem *c = start; c; ) {
				if ((*c).v - a[i] >= 0 && wh[(*c).v-a[i]] == NULL) {
					c = pop(c);
				} else {
					c = (*c).next;
				}
			}
		}
	}

	printf("%d\n",s.size());
	for (int i = 0; i<s.size(); ++i) printf("%d\n",s[i]);
	return 0;
}