#include #include using namespace std; int n; vector w; vector dp(10001, false); int main(){ int n, tmp, allw=0; cin >> n; for(int i = 0; i> tmp; w.push_back(tmp); allw += tmp; } //問題 //n/2が奇数では無理 //n個の中でちょうど重さが全体の重さ/2となる組み合わせを探せばいい //動的計画法でいけそう //左の重さを重ねていく //dp[左側の重さ]; //--jにすれば追加された数に対しての判定を行わない dp[0] = true; for(int i=0; i= 0; j--) { if(dp[j]) dp[j+w[i]] = true; } } if(allw%2 || !dp[allw/2]) cout << "impossible" << endl; else cout << "possible" << endl; }