1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int>v(1001);
vector<int> C;
vector<int> D;

int main()
{
	int z;
	long long s = 0;
	cin >> z;
	for (int i = 0; i < 1001; i++)
	{
		v[i] = 0;
	}
	for (int i = 0; i < z; i++)
	{
		int a;
		cin >> a;
		v[a]++;
	}
	for (int i = 0; i < 1001; i++)
	{
		if (v[i] > 0)
		{
			C.push_back(i);
			D.push_back(v[i]);
		}
		s += v[i] * i;
	}
	vector<bool>T(s + 1);
	for (int i = 0; i < T.size(); i++)
	{
		T[i] = false;
	}

	int n = C.size();
	int N = s;

	T[0] = true;

	int R = 0;
	for (int i = 0; i < n; i++) {
		for (int j = R; j >= 0; j--)
			if (T[j])
				for (int k = 1; k <= D[i] && j + k * C[i] <= N / 2; k++)
					if (T[j + k * C[i]])
						break;
					else
						T[j + k * C[i]] = true;

		R = min(N / 2, R + C[i] * D[i]);
	}
	for (long long o = N / 2; o >= 0; o--)
	{
		if (o == 0)
		{
			cout << "NIESTETY";
			break;
		}
		else if (T[o])
		{
			cout << o;
			break;
		}
	}
	return 0;
}