#include #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n; cin >> n; vector vec(n); int sum = 0; for (auto& i : vec) { cin >> i; sum += i; } sort(vec.begin(), vec.end(), greater()); if (sum % 2 == 1 || vec.at(0) > sum / 2) { cout << "impossible" << endl; return 0; } bool flag = false; //possibleならtrue vector y(sum + 1, 0); y.at(0) = 1; //check済 stack s; auto itr = vec.begin(); int weight = 0; while (true) { s.push(*itr); weight += s.top(); s.pop(); if (y.at(weight) == 0) { if (weight == sum / 2) { flag = true; break; } else if (weight < sum / 2) { y.at(weight) = 1; //check済 ++itr; } else { y.at(weight) = 1; //check済 weight -= static_cast(*itr); ++itr; } } if (itr == vec.end()) break; } cout << ((flag) ? "possible" : "impossible") << endl; return 0; } // 3 2 1 , sum=6 // 5 4 3 2 , sum=14 // 2 3 5 9 10 11 12 sum=52