結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー elphe
提出日時 2025-10-09 11:28:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,706 bytes
コンパイル時間 3,210 ms
コンパイル使用メモリ 293,508 KB
実行使用メモリ 766,148 KB
最終ジャッジ日時 2025-10-31 20:33:39
合計ジャッジ時間 10,969 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 3 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

[[nodiscard]] static inline constexpr std::tuple<std::array<std::vector<uint_least64_t>, 2>, std::vector<uint_least64_t>, std::vector<bool>, std::vector<uint_least32_t>> prepare(const uint_fast32_t N, const std::array<std::vector<uint_least32_t>, 2>& A) noexcept
{
	std::array<std::vector<uint_least64_t>, 2> csum_A = { std::vector<uint_least64_t>(N + 1, 0), std::vector<uint_least64_t>(N + 1, 0) };
	std::vector<uint_least64_t> csum_score(N + 1, 0);
	std::vector<bool> pos_on(N + 1, 0);
	std::vector<uint_least32_t> csum_switch(N + 1, 0);

	for (uint_fast32_t i = 0; i < N; ++i)
	{
		if (A[0][i] >= A[1][i])
			csum_score[i + 1] = csum_score[i] + A[pos_on[i + 1] = 0][i], csum_switch[i + 1] = csum_switch[i] + (pos_on[i] != 0);
		else
			csum_score[i + 1] = csum_score[i] + A[pos_on[i + 1] = 1][i], csum_switch[i + 1] = csum_switch[i] + (pos_on[i] != 1);
	}

	return std::make_tuple(std::move(csum_A), std::move(csum_score), std::move(pos_on), std::move(csum_switch));
}

// メモ化分枝限定法（TLEになってほしい）
[[nodiscard]] static inline uint_fast64_t solve(const uint_fast32_t N, const uint_fast32_t K, const std::array<std::vector<uint_least32_t>, 2>& A) noexcept
{
	const auto& [csum_A, csum_score, pos_on, csum_switch] = prepare(N, A);
	std::unordered_map<uint_least64_t, uint_least64_t> big_data;
	big_data.reserve(50'000'000);

	const auto dfs = [&](const auto self, const uint_fast32_t cur_phase = 0, const uint_fast32_t used_K = 0, const bool last_pos = 0, const uint_fast64_t cur_score = 0, const uint_fast64_t score_border = 0) constexpr noexcept -> uint_fast64_t
		{
			if (cur_phase == N) [[unlikely]]  // 最後まで探索した
				return cur_score;
			if (used_K == K) [[unlikely]]     // もう移動できない
				return cur_score + (csum_A[last_pos][N] - csum_A[last_pos][cur_phase]);
			if (K - used_K >= csum_switch[N] - csum_switch[cur_phase] + (pos_on[cur_phase] != last_pos)) [[unlikely]]  // もう燃料を気にする必要はない
				return cur_score + (csum_score[N] - csum_score[cur_phase]);
			if (cur_score + (csum_score[N] - csum_score[cur_phase]) <= score_border) [[unlikely]]  // どれだけ燃料があったとしても最大値を更新できない
				return score_border;
			if (!big_data.contains((cur_phase << 21) | (used_K << 1) | last_pos))
			{
				if (A[0][cur_phase] >= A[1][cur_phase])
				{
					const auto temp = self(self, cur_phase + 1, used_K + (last_pos != 0), 0, cur_score + A[0][cur_phase], score_border);
					big_data.insert({ (cur_phase << 21) | (used_K << 1) | last_pos, std::max<uint_fast64_t>(temp, self(self, cur_phase + 1, used_K + (last_pos != 1), 1, cur_score + A[1][cur_phase], std::max<uint_fast64_t>(score_border, temp))) - cur_score });
				}
				else
				{
					const auto temp = self(self, cur_phase + 1, used_K + (last_pos != 1), 1, cur_score + A[1][cur_phase], score_border);
					big_data.insert({ (cur_phase << 21) | (used_K << 1) | last_pos, std::max<uint_fast64_t>(temp, self(self, cur_phase + 1, used_K + (last_pos != 0), 0, cur_score + A[0][cur_phase], std::max<uint_fast64_t>(score_border, temp))) - cur_score });
				}
			}

			return cur_score + big_data[(cur_phase << 21) | (used_K << 1) | last_pos];
		};

	return dfs(dfs);
}

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

	uint_fast32_t T;
	std::cin >> T;
	for (uint_fast32_t i = 0; i < T; ++i)
	{
		uint_fast32_t N, K;
		std::cin >> N >> K;
		std::array<std::vector<uint_least32_t>, 2> A = { std::vector<uint_least32_t>(N), std::vector<uint_least32_t>(N) };
		for (auto& a : A[0]) std::cin >> a;
		for (auto& b : A[1]) std::cin >> b;

		std::cout << solve(N, K, A) << '\n';
	}

	return 0;
}
0