結果

問題 No.527 ナップサック容量問題
コンテスト
ユーザー lam6er
提出日時 2025-03-20 18:55:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 103 ms / 2,000 ms
コード長 1,315 bytes
コンパイル時間 271 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 64,508 KB
最終ジャッジ日時 2025-03-20 18:57:17
合計ジャッジ時間 3,873 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    idx +=1
    
    items = []
    sum_v = 0
    for _ in range(n):
        v = int(data[idx])
        w = int(data[idx+1])
        items.append((v, w))
        sum_v += v
        idx +=2
    V = int(data[idx])
    idx +=1
    
    if V == 0:
        min_w = min(w for v, w in items)
        min_ans = 1
        max_ans = min_w -1
        print(min_ans)
        print(max_ans)
        return
    
    max_possible_v = sum_v
    if V > max_possible_v:
        print(0)
        print('inf')
        return
    
    dp = [float('inf')] * (max_possible_v + 1)
    dp[0] = 0
    for (v_i, w_i) in items:
        for v in range(max_possible_v, v_i - 1, -1):
            if dp[v - v_i] + w_i < dp[v]:
                dp[v] = dp[v - v_i] + w_i
    
    if dp[V] == float('inf'):
        print(0)
        print('inf')
        return
    
    min_candidate = dp[V]
    
    min_T = float('inf')
    for v in range(V + 1, max_possible_v + 1):
        if dp[v] < min_T:
            min_T = dp[v]
    
    if min_T == float('inf'):
        max_ans = 'inf'
    else:
        max_ans = min_T -1
    
    print(min_candidate)
    print(max_ans if max_ans != 'inf' else 'inf')

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