結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー ID 21712
提出日時 2025-01-29 01:47:36
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 933 bytes
コンパイル時間 1,136 ms
コンパイル使用メモリ 97,556 KB
実行使用メモリ 814,512 KB
最終ジャッジ日時 2025-01-29 01:47:44
合計ジャッジ時間 7,745 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 MLE * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <cmath>

const int N_MAX = 500, D_MAX = 500, K_MAX = 500;
const long long INF = 1LL << 62;

int n, d, k;
int a[N_MAX], c[N_MAX];
long long dp[N_MAX+2][D_MAX+2][K_MAX+2];

void solve() {
	std::cin >> n >> d >> k;
	for (int i = 0; i < n; i++) std::cin >> a[i];
	for (int i = 0; i < n; i++) std::cin >> c[i];
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= d; j++)
			for (int x = 0; x <= k; x++)
				dp[i][j][x] = -INF;
	dp[0][0][0] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= d; j++) {
			for (int x = 0; x <= k; x++) {
				if (dp[i][j][x] == -INF) continue;
				dp[i+1][j][x] = std::max(dp[i+1][j][x], dp[i][j][x]);
				dp[i+1][j+1][std::min(k, x+c[i])] = std::max(dp[i+1][j+1][std::min(k, x+c[i])], dp[i][j][x]+(long long)a[i]);
			}
		}
	}
	if (dp[n][d][k] == -INF) std::cout << "No" << std::endl;
	else std::cout << dp[n][d][k] << std::endl;
}


int main() {
	solve();
	return 0;
}
0