結果

問題 No.3014 岩井満足性問題
ユーザー yamasaKit_
提出日時 2025-01-25 16:46:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,533 bytes
コンパイル時間 5,429 ms
コンパイル使用メモリ 279,024 KB
実行使用メモリ 7,088 KB
最終ジャッジ日時 2025-01-25 23:54:52
合計ジャッジ時間 5,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D, K;
    cin >> N >> D >> K;

    vector<long long> A(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    // 負の「無限大」の代わりに十分小さい値を使う (例: -1e15)
    const long long NEG_INF = -10000000000000000LL; // -1e16 程度

    // dp[j][k] = j 個の問題を選んで美しさが k のときの最大満足度
    // (D+1) x (K+1) のテーブル
    vector<vector<long long>> dp(D + 1, vector<long long>(K + 1, NEG_INF));
    dp[0][0] = 0; // まだ何も選んでいない状態

    for (int i = 0; i < N; i++) {
        vector<vector<long long>> dp2(D + 1, vector<long long>(K + 1, NEG_INF));
        long long a = A[i]; // 満足度
        long long c = C[i]; // 美しさ
        
        for (int j = 0; j < D; j++) {
            for (int k = 0; k <= K; k++) {
                if (dp[j][k] == NEG_INF) continue;

                // 問題 i を採用しない
                dp2[j][k] = max(dp2[j][k], dp[j][k]);

                // 問題 i を採用する
                int new_c = min<long long>(K, k + c);
                dp2[j + 1][new_c] = max(dp2[j + 1][new_c], dp[j][k] + a);
            }
        }

        // dp を更新
        dp = move(dp2);
    }

    long long ans = dp[D][K];
    if (ans == NEG_INF) {
        cout << "No\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}
0