結果

問題 No.626 Randomized 01 Knapsack
ユーザー lam6er
提出日時 2025-03-20 21:06:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 537 ms / 2,000 ms
コード長 2,672 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 98,940 KB
最終ジャッジ日時 2025-03-20 21:06:44
合計ジャッジ時間 5,994 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    W = int(input[idx+1])
    idx += 2
    items = []
    for _ in range(n):
        v = int(input[idx])
        w = int(input[idx+1])
        idx += 2
        if w > W:
            continue
        items.append((v, w))
    
    # Split items into heavy and light
    heavy = []
    light = []
    W_half = W // 2
    for v, w in items:
        if w > W_half:
            heavy.append((v, w))
        else:
            light.append((v, w))
    
    # Process light items using sparse DP
    dp = [(0, 0)]  # list of (weight, value) sorted by weight, with strictly increasing values
    for v_i, w_i in light:
        tmp = []
        for cw, cv in dp:
            new_w = cw + w_i
            new_v = cv + v_i
            if new_w <= W:
                tmp.append((new_w, new_v))
        
        # Merge tmp and current dp, then sort and apply dominance
        merged = []
        i = 0  # pointer for dp
        j = 0  # pointer for tmp
        while i < len(dp) and j < len(tmp):
            if dp[i][0] < tmp[j][0]:
                merged.append(dp[i])
                i += 1
            else:
                merged.append(tmp[j])
                j += 1
        while i < len(dp):
            merged.append(dp[i])
            i += 1
        while j < len(tmp):
            merged.append(tmp[j])
            j += 1
        
        # Apply dominance
        new_dp = []
        max_v = -1
        for w, v in merged:
            if v > max_v:
                # Remove previous entries with same weight
                if new_dp and new_dp[-1][0] == w:
                    new_dp.pop()
                new_dp.append((w, v))
                max_v = v
        dp = new_dp
    
    # Find base case value (no heavy items)
    base_case = 0
    left, right = 0, len(dp) - 1
    while left <= right:
        mid = (left + right) // 2
        if dp[mid][0] <= W:
            base_case = max(base_case, dp[mid][1])
            left = mid + 1
        else:
            right = mid - 1
    max_result = base_case
    
    # Check each heavy item
    for v_i, w_i in heavy:
        rem = W - w_i
        if rem < 0:
            continue
        best = 0
        left, right = 0, len(dp) - 1
        while left <= right:
            mid = (left + right) // 2
            if dp[mid][0] <= rem:
                best = max(best, dp[mid][1])
                left = mid + 1
            else:
                right = mid - 1
        current = v_i + best
        if current > max_result:
            max_result = current
    
    print(max_result)

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