結果

問題 No.2364 Knapsack Problem
コンテスト
ユーザー LyricalMaestro
提出日時 2025-04-12 17:52:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 78 ms / 3,000 ms
コード長 1,322 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 82,796 KB
実行使用メモリ 76,808 KB
最終ジャッジ日時 2025-04-12 17:52:27
合計ジャッジ時間 3,187 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2364

MIN_VALUE = -10 ** 18

def main():
    N, M, W = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))

    dp = [None for _ in range(2 ** (N + M))]
    for bit in range(2 ** (N + M)):
        weight = 0
        value = 0
        for i in range(N):
            if bit & (1 << i) > 0:
                weight += A[i]
                value += B[i]
        for i in range(M):
            if bit & (1 << (N + i)) > 0:
                weight -= C[i]
                value -= D[i]
        if 0 <= weight <= W:
            dp[bit] = value

    dp2 = [False] * (2 ** (N + M))
    dp2[0] = True
    for bit in range(2 ** (N + M)):
        if not dp2[bit]:
            continue

        for i in range(N + M):
            if (1 << i) & bit > 0:
                continue

            new_bit = (1 << i) | bit
            if dp[new_bit] is None:
                continue
        
            dp2[new_bit] |= dp2[bit]
    
    answer = MIN_VALUE
    for bit in range(2 ** (N + M)):
        if dp2[bit]:
            answer = max(answer, dp[bit])
    print(answer)
        

            
                    










    



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