結果
問題 | No.2317 Expression Menu |
ユーザー |
|
提出日時 | 2023-06-03 00:43:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,619 ms / 2,000 ms |
コード長 | 762 bytes |
コンパイル時間 | 327 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 298,160 KB |
最終ジャッジ日時 | 2024-12-29 01:50:21 |
合計ジャッジ時間 | 44,277 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
N, X, Y = map(int, input().split())A = [tuple(map(int, input().split())) for _ in range(N)]# dp[i][j][j]: i番目の機能までの実装/非実装が確定しており、メニュー枠をi、容量をj消費している時にあげられる可愛さの最大値。# 初期化: dp[i][j][k] = 0# 答え: max[0<=x<=X, 0<=y<=Y]{dp[N][x][y]}dp = [[[0] * (Y + 1) for _ in range(X+1)] for _ in range(N+1)]for i in range(N):a, b, c = A[i]for x in range(X+1):for y in range(Y+1):dp[i+1][x][y] = max(dp[i+1][x][y], dp[i][x][y])if x + a <= X and y + b <= Y:dp[i+1][x+a][y+b] = max(dp[i][x+a][y+b], dp[i][x][y] + c)# import pprint; pprint.pprint(dp)ans = 0for x in range(X+1):for y in range(Y+1):ans = max(ans, dp[N][x][y])print(ans)