#105150 (C++11) No.4 おもりと天秤

• 問題: No.4 おもりと天秤
• ユーザー: DAyamaCTF
• 提出日時: 2016-07-20 21:45:49
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 935 bytes
• コンパイル時間: 1,701 ms
• コンパイル使用メモリ: 144,136 KB
• 実行使用メモリ: 4,780 KB
• 最終ジャッジ日時: 2023-09-08 16:47:15
• 合計ジャッジ時間: 2,193 ms
• ジャッジサーバーID （参考情報）: judge12 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 4,700 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	3 ms; 4,576 KB
testcase_03	AC	3 ms; 4,536 KB
testcase_04	AC	3 ms; 4,504 KB
testcase_05	AC	4 ms; 4,548 KB
testcase_06	AC	3 ms; 4,576 KB
testcase_07	AC	4 ms; 4,496 KB
testcase_08	AC	1 ms; 4,380 KB
testcase_09	AC	4 ms; 4,528 KB
testcase_10	AC	3 ms; 4,596 KB
testcase_11	AC	3 ms; 4,504 KB
testcase_12	AC	3 ms; 4,780 KB
testcase_13	AC	3 ms; 4,536 KB
testcase_14	AC	3 ms; 4,540 KB
testcase_15	AC	3 ms; 4,732 KB
testcase_16	AC	3 ms; 4,500 KB
testcase_17	AC	3 ms; 4,596 KB
testcase_18	AC	4 ms; 4,540 KB
testcase_19	AC	4 ms; 4,600 KB
testcase_20	AC	4 ms; 4,548 KB
testcase_21	AC	4 ms; 4,532 KB
testcase_22	AC	4 ms; 4,500 KB

ソースコード

// g++ -std=c++11 temp.cpp
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define EACH(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3

#define MAX_N 1000

int n;
int w[100];
int sum = 0;
bool dp[111][11111];

int main(){
	cin>>n;
	REP(i,n){
		cin>>w[i];
		sum += w[i];
	}
	if(sum%2==1){
		cout<<"impossible"<<endl;
		return 0;
	}
	sum/=2;
	REP(i,111)REP(j,11111) dp[i][j] = false;
	dp[0][0] = true;
	REP(i,n){
		REP(j,11111){
			if(dp[i][j]){
				dp[i+1][j] = true;
				dp[i+1][j+w[i]] = true;
				//dbg(i); dbg(j);
			}
		}
	}
	if(dp[n][sum]) cout<<"possible"<<endl;
	else cout<<"impossible"<<endl;

	return 0;
}