結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー elphe
提出日時 2025-10-05 22:13:59
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,138 bytes
コンパイル時間 3,132 ms
コンパイル使用メモリ 279,484 KB
実行使用メモリ 18,624 KB
最終ジャッジ日時 2025-10-31 20:30:46
合計ジャッジ時間 7,792 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 2 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

// O(NK) 時間解法
[[nodiscard]] static inline constexpr uint_fast64_t solve(const uint_fast32_t N, const uint_fast32_t K, const std::vector<uint_least32_t>& A, const std::vector<uint_least32_t>& B) noexcept
{
	std::array<std::vector<std::array<uint_least64_t, 2>>, 2> dp = { std::vector<std::array<uint_least64_t, 2>>(K + 1, { 0, 0 }), std::vector<std::array<uint_least64_t, 2>>(K + 1, { A[0], B[0] }) };
	dp[1][0][1] = 0;
	for (uint_fast32_t i = 1; i < N; ++i)
		for (uint_fast32_t j = 1; j <= K; ++j)
			dp[(i & 1) ^ 1][j] = { std::max<uint_fast64_t>(dp[i & 1][j][0], dp[i & 1][j - 1][1]) + A[i], std::max<uint_fast64_t>(dp[i & 1][j - 1][0], dp[i & 1][j][1]) + B[i] };

	return std::max<uint_fast64_t>(dp[N & 1][K][0], dp[N & 1][K][1]);
}

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::vector<uint_least32_t> A(N), B(N);
		for (auto& a : A) std::cin >> a;
		for (auto& b : B) std::cin >> b;

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

	return 0;
}
0