結果

問題 No.3014 岩井満足性問題
ユーザー elphe
提出日時 2025-02-11 16:36:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 133 ms / 3,000 ms
コード長 811 bytes
コンパイル時間 1,406 ms
コンパイル使用メモリ 90,532 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-11 16:36:10
合計ジャッジ時間 2,740 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <vector>

using namespace std;

template<typename T> constexpr T chmax(T& variable, const T value) noexcept
{
	if (variable < value) return (variable = value);
	else return variable;
}

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

	int16_t N, D, K, i, j, k;
	cin >> N >> D >> K;
	vector<int32_t> A(N), C(N);
	for (i = 0; i != N; ++i) cin >> A[i];
	for (i = 0; i != N; ++i) cin >> C[i];

	vector<vector<int64_t>> dp(D + 1, vector<int64_t>(K + 1, INT64_MIN));
	dp[0][0] = 0;
	for (i = 0; i != N; ++i)
		for (j = D - 1; j >= 0; --j)
			for (k = K; k >= 0; --k)
				if (dp[j][k] != INT64_MIN)
					chmax(dp[j + 1][min<int32_t>(k + C[i], K)], dp[j][k] + A[i]);

	if (dp[D][K] == INT64_MIN) cout << "No\n";
	else cout << dp[D][K] << '\n';
	return 0;
}
0