Cod sursa(job #3246381)

Utilizator Commander_XDunel Stefan-Octavian Commander_X Data 2 octombrie 2024 20:24:19
Problema Economie Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
//https://www.infoarena.ro/problema/economie
#include <fstream>
#include <vector>
#include <stack>

std::ifstream fin("economie.in");
std::ofstream fout("economie.out");

using namespace std;

vector<long long int> dp, v, f;
stack<long long int> S;

long long int max(long long int a,long long int b)
{
	return a > b ? a : b;
}
int main()
{
	long long int n, maxim = 0, cnt = 0;
	fin >> n;
	v.resize(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		fin >> v[i];
		maxim = max(maxim, v[i]);
	}
	dp.resize(maxim + 1, 0);
	for (int i = 1; i <= n; ++i)
	{
		if (dp[v[i]] == 0)
			dp[v[i]] = 1;
		for (int j = maxim - v[i]; j > 0; --j)
		{
			if (j % v[i] == 0 && j != v[i])
				dp[j] = 2;
			else
				if (dp[j] != 0)
					dp[j + v[i]] = 2;
		}
	}
	for (int i = 1; i <= maxim; ++i)
		if (dp[i] == 1)
		{
			++cnt;
			S.push(i);
		}
	fout << cnt << '\n';
	while (!S.empty())
	{
		fout << S.top() << '\n';
		S.pop();
	}
	return 0;
}