#include #include #include #include #include using namespace std; #define REP(i,first,last) for (int i=first;i weights; int dp[101][10001] = {}; bool solve(int idx, int total){ if (dp[idx][total] == 1) return false; if (idx >= N || total > half) { //ここのtotalは10000を超えないため大丈夫 dp[idx][total] = 1; return false; } int new_total = total + weights[idx]; if (new_total == half) return true; if (solve(idx+1, total) || solve(idx+1, new_total)) return true; dp[idx][total] = 1; return false; } int main(){ cin >> N; int val; int total = 0; REP(i,0,N) { cin >> val; weights.push_back(val); total += val; } if (total & 1) { cout << "impossible" << endl; } else { half = total >> 1; sort(weights.begin(), weights.end()); if (solve(0,0)) { cout << "possible" << endl; } else { cout << "impossible" << endl; } } }