結果

問題 No.4 おもりと天秤
コンテスト
ユーザー elphe
提出日時 2025-09-22 18:00:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,018 bytes
コンパイル時間 3,386 ms
コンパイル使用メモリ 281,720 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-22 18:00:19
合計ジャッジ時間 4,037 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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::array<std::vector<bool>, 2> dp = { std::vector<bool>(sum_W / 2 + 1, false), std::vector<bool>(sum_W / 2 + 1, false) };
	dp[0][0] = true;
	for (uint_fast32_t i = 0; i != N; ++i)
	{
		for (uint_fast32_t j = 0; j < std::min<uint_fast32_t>(W[i], sum_W / 2 + 1); ++j)
			dp[(i & 1) ^ 1][j] = dp[i & 1][j];
		for (uint_fast32_t j = std::min(W[i], sum_W / 2 + 1); j <= sum_W / 2; ++j)
			dp[(i & 1) ^ 1][j] = dp[i & 1][j] | dp[i & 1][j - W[i]];
	}

	if (dp[N & 1][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