結果
問題 | No.3014 岩井満足性問題 |
ユーザー |
|
提出日時 | 2025-01-25 14:58:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 699 ms / 3,000 ms |
コード長 | 736 bytes |
コンパイル時間 | 3,505 ms |
コンパイル使用メモリ | 283,936 KB |
実行使用メモリ | 7,072 KB |
最終ジャッジ日時 | 2025-01-25 23:37:50 |
合計ジャッジ時間 | 6,854 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll signed main() { int n, d, k; cin >> n >> d >> k; vector<int> a(n), c(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> c[i]; } vector<vector<int>> dp(d+1, vector<int>(k+1, LLONG_MIN)); dp[0][0] = 0; for (int i = 0; i < n; i++) { auto ndp = dp; for (int j = 0; j < d; j++) { for (int l = 0; l <= k; l++) { if (dp[j][l] == LLONG_MIN) continue; int t = min(k, l + c[i]); ndp[j+1][t] = max(ndp[j+1][t], dp[j][l] + a[i]); } } dp = ndp; } if (dp[d][k] == LLONG_MIN) { cout << "No" << endl; } else { cout << dp[d][k] << endl; } }