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

• 問題: No.4 おもりと天秤
• ユーザー: kei
• 提出日時: 2016-08-11 18:20:35
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 4 ms / 5,000 ms
• コード長: 1,044 bytes
• コンパイル時間: 640 ms
• コンパイル使用メモリ: 67,128 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-26 09:51:16
• 合計ジャッジ時間: 1,513 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	3 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	4 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	4 ms; 5,376 KB
testcase_10	AC	4 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	2 ms; 5,376 KB
testcase_14	AC	2 ms; 5,376 KB
testcase_15	AC	3 ms; 5,376 KB
testcase_16	AC	2 ms; 5,376 KB
testcase_17	AC	2 ms; 5,376 KB
testcase_18	AC	4 ms; 5,376 KB
testcase_19	AC	3 ms; 5,376 KB
testcase_20	AC	4 ms; 5,376 KB
testcase_21	AC	4 ms; 5,376 KB
testcase_22	AC	4 ms; 5,376 KB

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

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;
}