結果

問題 No.3401 Large Knapsack Problem
コンテスト
ユーザー LyricalMaestro
提出日時 2025-12-28 05:17:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 976 ms / 2,000 ms
コード長 1,846 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 413 ms
コンパイル使用メモリ 82,772 KB
実行使用メモリ 239,844 KB
最終ジャッジ日時 2025-12-28 05:18:35
合計ジャッジ時間 33,832 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

def calc_gcd(A, B):
    """
    正の整数A, Bの最大公約数を計算する
    """
    a = max(A, B)
    b = min(A, B)
    while a % b > 0:
        c = a % b
        a = b
        b = c
    return b


from functools import cmp_to_key

# 比較関数
def compare_items(a, b):
    if a[0] * b[1] > b[0] * a[1]:
        return 1
    elif a[0] * b[1] < b[0] * a[1]:
        return -1
    else:
        return 0



def main():
    N, W = map(int, input().split())
    vw = []
    for _ in range(N):
        v, w = map(int, input().split())
        vw.append((v, w))
    
    # wについて一意にする
    w_map = {}
    for v, w in vw:
        if w not in w_map:
            w_map[w] = -1
        w_map[w] = max(v, w_map[w])
    
    new_wv = list([(key, value) for key, value in w_map.items()])
    
    # カスタム比較関数を使ってリストをソート
    new_wv = sorted(new_wv, key=cmp_to_key(compare_items))
    max_w, max_v = new_wv[0]

    w0 = max([w for w, _ in new_wv]) * max([w for w, _ in new_wv])
    border_w = min(w0, W)
    
    dp = [-1] * (border_w + 1)
    dp[0] = 0
    for w, v in new_wv:
        new_dp = [-1] * (border_w + 1)
        
        xx = [-1] * w
        for x in range(border_w + 1):
            y0 = x // w
            y1 = x % w
            if dp[x] >= 0:
                new_dp[x] = max(new_dp[x], dp[x])
                xx[y1] = max(xx[y1], dp[x] - y0 * v)

            if xx[y1] >= 0:
                new_dp[x] = max(new_dp[x], xx[y1] + y0 * v)

        dp = new_dp
    
    answer = -1
    for w in reversed(range(border_w + 1)):
        if dp[w] >= 0:
            w1 = W - w
            count = w1 // max_w
            ans = dp[w] + count * max_v
            answer = max(answer, ans)
    print(answer)



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