#include #include #include #include //2分探索木 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // キュー 優先度付きキュー #include #include #include #ifdef LOCAL #include "UnionFind.h"//同じグループに属するか #include "Prime.h"//素数判定 #include "RMQ.h"//区間最小値 #include "BIT.h"//累積和 #endif using namespace std; //conversion //------------------------------------------ inline long long toInt(string s) { long long v; istringstream sin(s); sin >> v; return v; } template inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); } //math //------------------------------------------- template inline T sqr(T x) { return x * x; } //typedef //------------------------------------------ typedef vector VI; typedef vector VVI; typedef vector VS; typedef pair PII; typedef long long LL; typedef vector VLL; typedef vector VPII; //container util //------------------------------------------ #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define MP make_pair #define SZ(a) int((a).size()) #define EACH(t,c) for(typeof((c).begin()) t=(c).begin(); t!=(c).end(); ++t) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define SORT(c) sort((c).begin(),(c).end()) //repetition //------------------------------------------ #define FOR(t,a,b) for(int t=(a);t<(b);++t) #define REP(t,n) FOR(t,0,n) //constant //------------------------------------------ const double EPS = 1e-10; const double PI = acos(-1.0); //clear memory //------------------------------------------ #define CLR(a) memset((a), 0 ,sizeof(a)) //debug //------------------------------------------ #if defined(__GNUC__) #include #define ASSERT_(x) assert(x) #else #include #define ASSERT_(x) assert(x) #endif #ifdef _DEBUG #define dump(x) cerr << #x << '=' << (x) << endl; #define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl; #define ASSERT(x) {if (!(x)){std::cerr << "\nError!!\n" << "info string file:" << __FILE__ << " line:" << __LINE__ <<" "<< #x<< std::endl;ASSERT_(x);}} #else #define ASSERT(x) ((void)0) #define debug(x) ((void)0) #define dump(x) ((void)0) #endif // _DEBUG template void showVector(vector& v) { for (int i = 0; i < v.size(); ++i) cerr << v[i] << " "; cerr << endl; } //mod //------------------------------------------- const LL mod = 1000000007; LL mod_pow(LL x, LL n, LL mod) { if (n == 0) { return 1; } LL res = mod_pow(x * x % mod, n / 2, mod); if (n & 1) { res = res * x % mod; } return res; } //bitop //------------------------------------------- #if defined(__GNUC__) #include int popcount(int a) { return __builtin_popcount(a); } #elif defined(_MSC_VER) #include int popcount(int a) { return __popcnt(a); } #endif //gcd lcm //------------------------------------------- LL gcd(LL a, LL b) { if (a%b == 0) { return b; } else return gcd(b, a%b); } LL lcm(LL a, LL b) { return a / gcd(a, b)*b; } //YES_NO //------------------------------------------ #define Yes_ cout<<"Yes"< class matrix : public vector< vector > { private: int tate_, yoko_; public: matrix(const int tate__, const int yoko__) { ASSERT(tate__ > 0); ASSERT(yoko__ > 0); this->resize(tate__); for (size_t i = 0; i < this->size(); i++) { (*this)[i].resize(yoko__); } tate_ = tate__; yoko_ = yoko__; } matrix() {}; int tate()const { return tate_; } int yoko()const { return yoko_; } void resizematrix(const int tate__, const int yoko__) { ASSERT(tate__ > 0); ASSERT(yoko__ > 0); this->resize(tate__); for (size_t i = 0; i < this->size(); i++) { (*this)[i].resize(yoko__); } tate_ = tate__; yoko_ = yoko__; } void setone() {for (int i = 0; i < tate(); i++) for (int j = 0; j < yoko(); j++) { (*this)[i][j] = 1; }} void setzero() {for (int i = 0; i < tate(); i++) for (int j = 0; j < yoko(); j++) { (*this)[i][j] = 0; }} void setAll(T a) {for (int i = 0; i < tate(); i++) for (int j = 0; j < yoko(); j++) { (*this)[i][j] = a; }} }; template std::ostream& operator<<(std::ostream& os, const matrix& m) { for (int j = 0; j < m.tate(); j++) { for (int i = 0; i < m.yoko(); i++) { os << (int)m[j][i]; } os << endl; } return os; } //time //------------------------------------------ #if defined(__GNUC__) #include #include #include LL starttime; inline LL now() { struct timeval tv; gettimeofday(&tv, NULL); LL t = tv.tv_sec * 1000LL + tv.tv_usec / 1000LL; return t; } inline LL elapsed() { return now() - starttime; } #else #include #include typedef std::chrono::milliseconds::rep TimePoint; inline TimePoint now() { return std::chrono::duration_cast(std::chrono::steady_clock::now().time_since_epoch()).count(); } TimePoint starttime; inline TimePoint elapsed() { return now() - starttime; } #endif //===================================================== //A[i][j]= [i]番目の重りまでを用いて重さjを作成できるか // A[i][j]= A[i-1][j] |A[i-1][j-W[i]] bool A[101][101010] = {0}; int main() { int N; cin >> N; VI W(N); int sum = 0; REP(i, N) { cin >> W[i]; sum += W[i]; } if (sum % 2) { cout << "impossible" << endl; exit(0); } sum /= 2; A[0][0] = true; REP(i, N) { A[i][0] = true; } FOR(i,1, N+1)REP(j, sum+1) { A[i][j] = A[i-1][j]; if (j - W[i-1] >= 0) { A[i][j] |= A[i - 1][j - W[i - 1]]; } } if (A[N][sum]) { cout << "possible" << endl; } else { cout << "impossible" << endl; } }