結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー elphe
提出日時 2025-09-17 12:26:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,054 bytes
コンパイル時間 3,055 ms
コンパイル使用メモリ 281,404 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-17 12:26:34
合計ジャッジ時間 16,559 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

[[nodiscard]] static inline constexpr std::pair<std::vector<uint_least32_t>, std::vector<uint_least32_t>> prepare(const uint_fast32_t N, const std::vector<uint_least32_t>& v, const std::vector<uint_least32_t>& w) noexcept
{
	std::vector<uint_least32_t> csum_v(N + 1, 0), csum_w(N + 1, 0);
	for (uint_fast32_t i = 0; i < N; ++i)
		csum_v[i + 1] = csum_v[i] + v[i];
	for (uint_fast32_t i = 0; i < N; ++i)
		csum_w[i + 1] = csum_w[i] + w[i];

	return std::make_pair(std::move(csum_v), std::move(csum_w));
}

[[nodiscard]] static inline constexpr std::vector<uint_least32_t> solve(const uint_fast32_t N, const uint_fast32_t W, const std::vector<uint_least32_t>& v, const std::vector<uint_least32_t>& w) noexcept
{
	const auto [csum_v, csum_w] = prepare(N, v, w);
	std::vector<uint_least32_t> ans, cur;
	uint_fast32_t max_value = 0, cur_value = 0, cur_weight = 0;

	const auto dfs = [&](const auto self, const uint_fast32_t cur_pos = 0) constexpr noexcept -> void
		{
			if (cur_pos == N) [[unlikely]]
			{
				if (max_value < cur_value)
					max_value = cur_value, ans = cur;
				return;
			}

			if (cur_value + (csum_v[N] - csum_v[cur_pos]) <= max_value) [[unlikely]]
				return;

			if (cur_weight + (csum_w[N] - csum_w[cur_pos]) > W) [[likely]]
				self(self, cur_pos + 1);
			
			if (cur_weight + w[cur_pos] <= W)
			{
				cur.push_back(cur_pos + 1), cur_value += v[cur_pos], cur_weight += w[cur_pos];
				self(self, cur_pos + 1);
				cur.pop_back(), cur_value -= v[cur_pos], cur_weight -= w[cur_pos];
			}
		};

	dfs(dfs);
	return ans;
}

static inline void output(const std::vector<uint_least32_t>& ans) noexcept
{
	std::cout << ans.size() << '\n' << ans[0];
	for (uint_fast32_t i = 1; i < ans.size(); ++i)
		std::cout << ' ' << ans[i];
	std::cout << '\n';
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);

	uint_fast32_t N, W;
	std::cin >> N >> W;
	std::vector<uint_least32_t> v(N), w(N);
	for (auto& v : v) std::cin >> v;
	for (auto& w : w) std::cin >> w;

	output(solve(N, W, v, w));
	return 0;
}
0