/* N, D, K = map(int, input().split()) A = list(map(int, input().split())) C = list(map(int, input().split())) INF = -10**20 dp = [[INF for col in range(N + 1)] for row in range(K + 1)] dp[0][0] = 0 for sel in range(D + 1): ne_dp = [[INF for col in range(N + 1)] for row in range(K + 1)] for col in range(N): for row in range(K + 1): if dp[row][col] != INF: # 選ぶ if sel != D: ne_row = row + C[col] ne_row = min(ne_row, K) if ne_dp[ne_row][col + 1] == INF: ne_dp[ne_row][col + 1] = dp[row][col] + A[col] else: ne_dp[ne_row][col + 1] = max(ne_dp[ne_row][col + 1], dp[row][col] + A[col]) # 選ばない if dp[row][col + 1] == INF: dp[row][col + 1] = dp[row][col] else: dp[row][col + 1] = max(dp[row][col + 1], dp[row][col]) if sel != D: dp = ne_dp ans = INF for col in range(N + 1): if dp[K][col] != INF: ans = max(ans, dp[K][col]) if ans == INF: print("No") else: print(ans) */ #include #include #include using namespace std; const long long INF = -1e20; 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(K + 1, vector(N + 1, INF)); dp[0][0] = 0; for (int sel = 0; sel <= D; sel++) { vector> ne_dp(K + 1, vector(N + 1, INF)); for (int col = 0; col < N; col++) { for (int row = 0; row <= K; row++) { if (dp[row][col] != INF) { // 選ぶ if (sel != D) { int ne_row = row + C[col]; ne_row = min(ne_row, K); if (ne_dp[ne_row][col + 1] == INF) { ne_dp[ne_row][col + 1] = dp[row][col] + A[col]; } else { ne_dp[ne_row][col + 1] = max(ne_dp[ne_row][col + 1], dp[row][col] + A[col]); } } // 選ばない if (dp[row][col + 1] == INF) { dp[row][col + 1] = dp[row][col]; } else { dp[row][col + 1] = max(dp[row][col + 1], dp[row][col]); } } } } if (sel != D) { dp = move(ne_dp); } } long long ans = INF; for (int col = 0; col <= N; col++) { if (dp[K][col] != INF) { ans = max(ans, dp[K][col]); } } if (ans == INF) { cout << "No" << endl; } else { cout << ans << endl; } return 0; }