/* 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 #include #include #include using namespace std; int main() { int N, D, K; cin >> N >> D >> K; vector A(N); vector C(N); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < N; i++) cin >> C[i]; vector>> dp(D + 1, vector>(K + 1, vector(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::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::min()) { cout << "No" << endl; } else { cout << ans << endl; } return 0; }