結果

問題 No.3014 岩井満足性問題
ユーザー u_kun
提出日時 2025-01-25 13:38:55
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,474 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 82,884 KB
実行使用メモリ 268,856 KB
最終ジャッジ日時 2025-01-25 22:53:42
合計ジャッジ時間 10,782 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge9
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

dp = [[None for col in range(N + 1)] for row in range(K + 1)]
dp[0][0] = 0

for sel in range(D + 1):
    
    ne_dp = [[None 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] != None:
                
                # 選ぶ
                if sel != D:
                    ne_row = row + C[col]
                    ne_row = min(ne_row, K)
                    
                    if ne_dp[ne_row][col + 1] == None:
                        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] == None:
                    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 = -10**20

for col in range(N + 1):
    if dp[K][col] != None:
        ans = max(ans, dp[K][col])

if ans == -10**20:
    print("No")
else:
    print(ans)
0