#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; }
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; } |