結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー elphe
提出日時 2025-10-09 11:10:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,881 bytes
コンパイル時間 2,920 ms
コンパイル使用メモリ 286,380 KB
実行使用メモリ 38,400 KB
最終ジャッジ日時 2025-10-31 20:33:31
合計ジャッジ時間 9,268 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 3 TLE * 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 constexpr 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);

	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)  // 最後まで探索した
				return cur_score;
			if (used_K == K)     // もう移動できない
				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))  // もう燃料を気にする必要はない
				return cur_score + (csum_score[N] - csum_score[cur_phase]);
			if (cur_score + (csum_score[N] - csum_score[cur_phase]) <= score_border)  // どれだけ燃料があったとしても最大値を更新できない
				return score_border;

			const auto temp = self(self, cur_phase + 1, used_K + (last_pos != 0), 0, cur_score + A[0][cur_phase], score_border);
			return 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)));
		};

	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