結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー elphe
提出日時 2025-02-11 16:25:32
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 151 ms / 3,000 ms
コード長 889 bytes
コンパイル時間 986 ms
コンパイル使用メモリ 90,680 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-02-11 16:25:35
合計ジャッジ時間 2,553 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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<pair<int32_t, int32_t>> problems(N);
	for (auto& problem : problems) cin >> problem.first;
	for (auto& problem : problems) cin >> problem.second;

	vector<vector<int64_t>> dp(D + 1, vector<int64_t>(K + 1, INT64_MIN));
	dp[0][0] = 0;
	for (const auto& problem : problems)
		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 + problem.second, K)], dp[j][k] + problem.first);

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