結果

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

ソースコード

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

def cmp(r1, r2):
    return r1[0] * r2[1] == r2[0] * r1

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])
    
    # v / w について同じものがあった場合はwが小さい方を優先する
    rate_map = {}
    for w, v in w_map.items():
        gcd = calc_gcd(w, v)

        w0 = w // gcd
        v0 = v // gcd
        if (w0, v0) not in rate_map:
            rate_map[(w0, v0)] = (w, v)
        else:
            if rate_map[(w0, v0)][0] > w:
                rate_map[(w0, v0)] = (w, v)
    
    new_wv = list(rate_map.values())

    # カスタム比較関数を使ってリストをソート
    new_wv = sorted(new_wv, key=cmp_to_key(compare_items))

    max_w, max_v = new_wv[0]

    w0 = -1
    for w, v in new_wv:
        w0 = max(w0, w)
    
    border_w = min(w0 ** 2, 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 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