結果

問題 No.3014 岩井満足性問題
ユーザー u_kun
提出日時 2025-01-25 13:16:22
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,462 bytes
コンパイル時間 507 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 889,612 KB
最終ジャッジ日時 2025-01-25 22:41:00
合計ジャッジ時間 19,765 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 3 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)] for sel in range(D + 1)]
dp[0][0][0] = 0

for sel in range(D + 1):
    
    for col in range(N):
        for row in range(K + 1):
            
            if dp[sel][row][col] != None:
                
                # 選ぶ
                if sel != D:
                    ne_row = row + C[col]
                    ne_row = min(ne_row, K)
                    
                    if dp[sel + 1][ne_row][col + 1] == None:
                        dp[sel + 1][ne_row][col + 1] = dp[sel][row][col] + A[col]
                    else:
                        dp[sel + 1][ne_row][col + 1] = max(dp[sel + 1][ne_row][col + 1], dp[sel][row][col] + A[col])
                    
                
                # 選ばない
                if dp[sel][row][col + 1] == None:
                    dp[sel][row][col + 1] = dp[sel][row][col]
                else:
                    dp[sel][row][col + 1] = max(dp[sel][row][col + 1], dp[sel][row][col])

ans = -10**20

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

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