結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー elphe
提出日時 2025-02-11 16:37:59
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 109 ms / 3,000 ms
コード長 802 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 980 ms
コンパイル使用メモリ 88,600 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-11 16:38:02
合計ジャッジ時間 2,305 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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);

	int64_t N, D, K, i, j, k;
	cin >> N >> D >> K;
	vector<int64_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(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