#include <cstdio> #include <cstdlib> #include <map> #include <vector> using namespace std; bool map_get(map<int, bool> map, int key) { if (map.find(key) == map.end()) { return false; } else { return map[key]; } } int main() { int n; int result = 0; vector<int> input; map<int, bool> dp; int sum = 0; scanf("%d", &n); input.reserve(n); for(int i = 0; i < n; ++i) { int x; scanf("%d", &x); input.push_back(x); } for (vector<int>::iterator it = input.begin(); it != input.end(); it++) { sum += *it; } dp[0] = true; for (vector<int>::iterator it = input.begin(); it != input.end(); it++) { for (int j = sum - *it; j >= 0; j--) { if (map_get(dp, j)) { dp[j + *it] = true; } } } for (map<int, bool>::iterator it = dp.begin(); it != dp.end(); it++) { int m = it->first * 2; if (map_get(dp, m) && result < m) { result = m; } } if (result > 0) { printf("%d\n", result); } else { printf("NIESTETY\n"); } }
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 | #include <cstdio> #include <cstdlib> #include <map> #include <vector> using namespace std; bool map_get(map<int, bool> map, int key) { if (map.find(key) == map.end()) { return false; } else { return map[key]; } } int main() { int n; int result = 0; vector<int> input; map<int, bool> dp; int sum = 0; scanf("%d", &n); input.reserve(n); for(int i = 0; i < n; ++i) { int x; scanf("%d", &x); input.push_back(x); } for (vector<int>::iterator it = input.begin(); it != input.end(); it++) { sum += *it; } dp[0] = true; for (vector<int>::iterator it = input.begin(); it != input.end(); it++) { for (int j = sum - *it; j >= 0; j--) { if (map_get(dp, j)) { dp[j + *it] = true; } } } for (map<int, bool>::iterator it = dp.begin(); it != dp.end(); it++) { int m = it->first * 2; if (map_get(dp, m) && result < m) { result = m; } } if (result > 0) { printf("%d\n", result); } else { printf("NIESTETY\n"); } } |