結果
問題 |
No.3014 岩井満足性問題
|
ユーザー |
![]() |
提出日時 | 2025-09-06 10:30:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,984 bytes |
コンパイル時間 | 3,380 ms |
コンパイル使用メモリ | 283,528 KB |
実行使用メモリ | 814,464 KB |
最終ジャッジ日時 | 2025-09-06 10:31:03 |
合計ジャッジ時間 | 8,653 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 MLE * 2 -- * 4 |
ソースコード
// ======================== ORIGINAL PYTHON CODE (AS REQUIRED) ======================== // from heapq import heappop, heappush, heapify // from bisect import bisect // #from sortedcontainers import SortedList // from collections import deque, defaultdict // from math import floor, ceil, isqrt, comb // from sys import stdin, setrecursionlimit // #setrecursionlimit(10**7) // intin = lambda: int(stdin.readline()) // strin = lambda: stdin.readline().rstrip() // listin = lambda: list(map(int, stdin.readline().split())) // tuplein = lambda m: [tuple(map(lambda x: int(x) if x.isdigit() or (len(x) > 1 and x[0] == "-" and x[1:].isdigit()) else x, stdin.readline().split())) for _ in range(m)] // gridin = lambda m: [list(map(int, stdin.readline().split())) for _ in range(m)] // strgridin = lambda h: [stdin.readline().rstrip() for _ in range(h)] // mapin = lambda: map(int, stdin.readline().split()) // N, D, K = mapin() // A = listin() // C = listin() // dp = [[[-float("inf")] * (K + 1) for _ in range(D + 1)] for _ in range(N + 1)] // #dp[i][j][k] = i番目まで見たとき、jことったとき美しさがkであるときの満足度の最大値 // dp[0][0][0] = 0 // for i in range(N): // for j in range(D + 1): // for k in range(K + 1): // dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k]) // if j + 1 <= D: // dp[i+1][j+1][min(K,k+C[i])] = max(dp[i+1][j+1][min(K,k+C[i])], dp[i][j][k] + A[i]) // print(dp[N][D][K] if dp[N][D][K] != -float("inf") else "No") // ==================================================================================== #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, D, K; if (!(cin >> N >> D >> K)) return 0; 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]; const long long NEG = -(1LL << 60); // dp[i][j][k] = after seeing first i items, having taken j items, // and "beauty" k, the maximum satisfaction. vector<vector<vector<long long>>> dp( N + 1, vector<vector<long long>>(D + 1, vector<long long>(K + 1, NEG)) ); dp[0][0][0] = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j <= D; ++j) { for (int k = 0; k <= K; ++k) { // carry over dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]); // take current if possible if (j + 1 <= D) { int nk = min(K, k + (int)C[i]); if (dp[i][j][k] != NEG) { // prevent overflow; semantically equivalent to Python -inf behavior dp[i + 1][j + 1][nk] = max(dp[i + 1][j + 1][nk], dp[i][j][k] + A[i]); } } } } } long long ans = dp[N][D][K]; if (ans == NEG) { cout << "No\n"; } else { cout << ans << '\n'; } return 0; }