#include #include #include #include using namespace std; int main() { /* i番目の合計値m  存在する ⇒ true  存在しない ⇒ bool i:考慮した個数/ m:合計値 dp[i][m] = {dp[i - 1][m] , dp[i - 1][m - w[i]]} どちらかがtrue ⇒true i番目に合計値m i番目を値を考慮 i番目の値を考慮 */ int num; int w[101]; bool dp[101][10001] = { false }; int sum = 0; int bal_sum = 0; cin >> num; for (int i = 0; i < num;i++) { cin >> w[i]; sum += w[i]; } dp[0][w[0]] = true; if (sum % 2 == 1) { cout << "impossible" << endl; return 0; } sum /= 2; for (int i = 1;i < num;i++) { for (int m = 0; m < 10001; m++) { if (m - w[i] <= 0) { dp[i][m] = dp[i - 1][m]; continue; } if (dp[i - 1][m] == true || dp[i - 1][m - w[i]] == true) { dp[i][m] = true; continue; } dp[i][m] = false; } } if (dp[num - 1][sum] == true) { cout << "possible" << endl; } else { cout << "impossible" << endl; } return 0; }