結果

問題 No.3014 岩井満足性問題
ユーザー Kaira
提出日時 2025-01-25 14:21:21
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 765 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 1,048,920 KB
最終ジャッジ日時 2025-01-25 23:17:12
合計ジャッジ時間 28,899 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 1 WA * 2 RE * 5 TLE * 4 MLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#dp[i][j][k] = the maximum satisfaction for beauty >= j in {1,...,i} and choosing k problems
#If we choose i+1, then j -> j - beauty_i+1, k -> k-1
#if we dont, then j -> j, j -> j
#dp[i+1][j][k] = max(dp[i][j-beauty_i+1][k-1], dp[i][j][k])

dp = [[[-float("inf") for _ in range(D)] for _ in range(K)] for _ in range(N)]

for k in range(D):
  for j in range(K):
    dp[k][j][k] = sum(A[:k+1]) if sum(C[:k+1]) >= j+1 else -float("inf")

for i in range(N-1):
  for j in range(K):
    for k in range(D):
      dp[i+1][j][k] = max(A[i+1] + dp[i][j-C[i+1]][k-1], dp[i][j][k])

if dp[N-1][K-1][D-1] == -float("inf"):
  print('No')
else:
  print(dp[N-1][K-1][D-1])
0