結果

問題 No.2364 Knapsack Problem
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:08:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 629 ms / 3,000 ms
コード長 1,504 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 163,952 KB
最終ジャッジ日時 2025-03-20 21:08:21
合計ジャッジ時間 8,230 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    M = int(input[idx+1])
    W = int(input[idx+2])
    idx +=3
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    B = list(map(int, input[idx:idx+N]))
    idx +=N
    C = list(map(int, input[idx:idx+M]))
    idx +=M
    D = list(map(int, input[idx:idx+M]))
    idx +=M
    
    ops = []
    for i in range(N):
        ops.append((A[i], B[i]))
    for i in range(M):
        ops.append((-C[i], -D[i]))
    
    max_ops = N + M
    max_mask = 1 << max_ops
    
    dp = [ [-float('inf')] * (W +1) for _ in range(max_mask)]
    dp[0][0] = 0
    
    for mask in range(max_mask):
        for current_w in range(W +1):
            current_v = dp[mask][current_w]
            if current_v == -float('inf'):
                continue
            for op in range(max_ops):
                if (mask >> op) & 1:
                    continue
                delta_w, delta_v = ops[op]
                new_w = current_w + delta_w
                if new_w < 0 or new_w > W:
                    continue
                new_v = current_v + delta_v
                new_mask = mask | (1 << op)
                if new_v > dp[new_mask][new_w]:
                    dp[new_mask][new_w] = new_v
    
    max_value = 0
    for mask in range(max_mask):
        for w in range(W+1):
            if dp[mask][w] > max_value:
                max_value = dp[mask][w]
    print(max_value)

if __name__ == "__main__":
    main()
0