結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー Kaira
提出日時 2025-01-25 14:21:21
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
MLE  
実行時間 -
コード長 765 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 386 ms
コンパイル使用メモリ 84,772 KB
実行使用メモリ 1,201,548 KB
最終ジャッジ日時 2026-06-24 00:54:13
合計ジャッジ時間 11,332 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 2 MLE * 4 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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