結果

問題 No.4 おもりと天秤
ユーザー elphe
提出日時 2025-09-22 18:03:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 749 bytes
コンパイル時間 3,178 ms
コンパイル使用メモリ 279,040 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-22 18:04:00
合計ジャッジ時間 3,935 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

[[nodiscard]] static inline constexpr const char* solve(const uint_fast32_t N, const std::vector<uint_fast32_t>& W) noexcept
{
	const uint_fast32_t sum_W = std::accumulate(W.begin(), W.end(), UINT32_C(0));
	if (sum_W & 1) return "impossible";

	std::vector<bool> dp(sum_W / 2 + 1, false);
	dp[0] = true;
	for (uint_fast32_t i = 0; i != N; ++i)
		for (uint_fast32_t j = sum_W / 2; j >= W[i]; --j)
			dp[j] = dp[j] | dp[j - W[i]];

	if (dp[sum_W / 2]) return "possible";
	else return "impossible";
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t N;
	std::cin >> N;
	std::vector<uint_fast32_t> W(N);
	for (auto& w : W) std::cin >> w;

	std::cout << solve(N, W) << '\n';
	return 0;
}
0