結果

問題 No.4 おもりと天秤
コンテスト
ユーザー T.Stream
提出日時 2020-04-14 11:34:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 522 bytes
コンパイル時間 2,463 ms
コンパイル使用メモリ 198,072 KB
最終ジャッジ日時 2025-01-09 18:32:34
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
	long n,i,j,cur,res;
	cin >> n;
	vector<long> w(n);
	res=0;
	for(i=0; i<n; i++){
		cin >> w[i];
		res+=w[i];
	}
	if(res%2==1){
		cout << "impossible" << endl; return 0;
	}
	vector<bool> p1(res+1,false),p2(res+1,false);
	p1[0]=true; p2[0]=true;
	cur=0;
	for(i=0; i<n; i++){
		for(j=0; j<=cur; j++){
			p2[j+w[i]]=p1[j+w[i]] | p1[j];
		}
		cur+=w[i];
		p1=p2;
	}
	if(p1[res/2]){
		cout << "possible" << endl;
	}else{
		cout << "impossible" << endl;
	}
	return 0;
}
0