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

• 問題: No.4 おもりと天秤
• ユーザー: dgd1724
• 提出日時: 2016-11-22 06:49:02
• 言語: C++11 (gcc 13.3.0)
• 結果: TLE
• 実行時間: -
• コード長: 1,103 bytes
• コンパイル時間: 1,399 ms
• コンパイル使用メモリ: 159,188 KB
• 実行使用メモリ: 10,496 KB
• 最終ジャッジ日時: 2024-11-27 09:36:19
• 合計ジャッジ時間: 56,186 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

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

ソースコード

#include <bits/stdc++.h>

//const static double	de_PI	= 3.14159265358979323846;
//const static double	de_EPS	= 0.000001;
//const static int	de_MOD = 1000000007;
//const static int	de_MAX = 999999999;
//const static int	de_MIN = -999999999;

inline void Increase_Binary(std::bitset<100> &a) {

	unsigned int i = 0;
	while (1) {
		if (a[i] == 0) {
			a[i] = 1;
			break;
		}
		else {
			a[i] = 0;
			i++;
		}
	}
}

int main(void) {

	//std::ifstream inf("123.txt");	std::cin.rdbuf(inf.rdbuf());

	int N = 0;
	std::cin >> N;
	std::valarray<int> W(N);
	for (int i = 0; i < N; i++) { std::cin >> W[i]; }

	if (W.sum() % 2 != 0) {
		std::cout << "impossible" << std::endl;
		return 0;
	}

	int half = N / 2, count = 0, sum = 0, compare = W.sum() / 2;
	std::bitset<100> flg;
	while (1) {
		Increase_Binary(flg);
		count = flg.count();
		if (count == N) { break; }
		if (count > half) { continue; }

		sum = 0;
		for (int i = 0; i < N; i++) {
			if (flg[i]) { sum += W[i]; }
		}

		if (sum == compare) {
			std::cout << "possible" << std::endl;
			return 0;
		}
	}

	std::cout << "impossible" << std::endl;

}