結果
問題 | No.3014 岩井満足性問題 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}