結果

問題 No.3014 岩井満足性問題
ユーザー u_kun
提出日時 2025-01-25 13:23:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,066 bytes
コンパイル時間 1,051 ms
コンパイル使用メモリ 106,328 KB
実行使用メモリ 504,320 KB
最終ジャッジ日時 2025-01-25 22:45:19
合計ジャッジ時間 4,342 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 10 MLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
Original Python Code:

N, D, K = map(int, input().split())
A = list(map(int, input().split()))
C = list(map(int, input().split()))

dp = [[[None for col in range(N + 1)] for row in range(K + 1)] for sel in range(D + 1)]
dp[0][0][0] = 0

for sel in range(D + 1):
    for col in range(N):
        for row in range(K + 1):
            if dp[sel][row][col] != None:
                # 選ぶ
                if sel != D:
                    ne_row = row + C[col]
                    ne_row = min(ne_row, K)
                    if dp[sel + 1][ne_row][col + 1] == None:
                        dp[sel + 1][ne_row][col + 1] = dp[sel][row][col] + A[col]
                    else:
                        dp[sel + 1][ne_row][col + 1] = max(dp[sel + 1][ne_row][col + 1], dp[sel][row][col] + A[col])
                # 選ばない
                if dp[sel][row][col + 1] == None:
                    dp[sel][row][col + 1] = dp[sel][row][col]
                else:
                    dp[sel][row][col + 1] = max(dp[sel][row][col + 1], dp[sel][row][col])

ans = -10**20
for col in range(N + 1):
    if dp[D][K][col] != None:
        ans = max(ans, dp[D][K][col])

if ans == -10**20:
    print("No")
else:
    print(ans)
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    int N, D, K;
    cin >> N >> D >> K;
    
    vector<int> A(N);
    vector<int> C(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> C[i];
    
    vector<vector<vector<int>>> dp(D + 1, vector<vector<int>>(K + 1, vector<int>(N + 1, -1)));
    dp[0][0][0] = 0;
    
    for (int sel = 0; sel <= D; sel++) {
        for (int col = 0; col < N; col++) {
            for (int row = 0; row <= K; row++) {
                if (dp[sel][row][col] != -1) {
                    // 選ぶ
                    if (sel != D) {
                        int ne_row = row + C[col];
                        ne_row = min(ne_row, K);
                        
                        if (dp[sel + 1][ne_row][col + 1] == -1) {
                            dp[sel + 1][ne_row][col + 1] = dp[sel][row][col] + A[col];
                        } else {
                            dp[sel + 1][ne_row][col + 1] = max(dp[sel + 1][ne_row][col + 1], dp[sel][row][col] + A[col]);
                        }
                    }
                    
                    // 選ばない
                    if (dp[sel][row][col + 1] == -1) {
                        dp[sel][row][col + 1] = dp[sel][row][col];
                    } else {
                        dp[sel][row][col + 1] = max(dp[sel][row][col + 1], dp[sel][row][col]);
                    }
                }
            }
        }
    }
    
    int ans = numeric_limits<int>::min();
    for (int col = 0; col <= N; col++) {
        if (dp[D][K][col] != -1) {
            ans = max(ans, dp[D][K][col]);
        }
    }
    
    if (ans == numeric_limits<int>::min()) {
        cout << "No" << endl;
    } else {
        cout << ans << endl;
    }
    
    return 0;
}
0