結果
問題 |
No.3014 岩井満足性問題
|
ユーザー |
![]() |
提出日時 | 2025-02-22 03:32:37 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 856 bytes |
コンパイル時間 | 9,441 ms |
コンパイル使用メモリ | 171,476 KB |
実行使用メモリ | 814,464 KB |
最終ジャッジ日時 | 2025-02-22 03:32:51 |
合計ジャッジ時間 | 9,979 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 MLE * 2 -- * 4 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ll N, D, K; cin >> N >> D >> K; vector<ll> A(N), C(N); for (auto&& a : A) cin >> a; for (auto&& c : C) cin >> c; ll inf = -100000000000ll; // dp[i][j][k]:=i番目まで見てj個の問題案を採用したときに美しさがk vector dp(N + 1, vector(D + 1, vector<ll>(K + 1, inf))); dp[0][0][0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= D; j++) { for (int k = 0; k <= K; k++) if (dp[i][j][k] != inf) { dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]); if (j != D) { auto& a = dp[i + 1][j + 1][min(K, k + C[i])]; a = max(a, dp[i][j][k] + A[i]); } } } } if (dp[N][D][K] == inf) { cout << "No\n"; } else { cout << dp[N][D][K] << endl; } }