結果

問題 No.2617 容量3のナップザック
ユーザー qwewe
提出日時 2025-05-14 13:22:51
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,409 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 173,936 KB
最終ジャッジ日時 2025-05-14 13:25:09
合計ジャッジ時間 13,922 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N, K, seed, a, b, m = map(int, sys.stdin.readline().split())

    f_values = [0] * (2 * N)
    
    # Constraints: 1 <= K <= N <= 10^6, so N is at least 1.
    # Thus, 2*N is at least 2, so f_values will have at least 2 elements if N=1.
    # The list f_values will be indexed 0 to 2*N-1.
    
    f_values[0] = seed
    for i in range(2 * N - 1): # Computes f_values[1] through f_values[2*N-1]
        f_values[i+1] = (a * f_values[i] + b) % m

    items1_vals = [] # Values of items with weight 1
    items2_vals = [] # Values of items with weight 2
    items3_vals = [] # Values of items with weight 3

    # Note on indexing: problem uses 1-based, Python uses 0-based.
    # f_i (1-based) corresponds to f_values[i-1] (0-based).
    # w_i = f_i % 3 + 1
    # v_i = w_i * f_{N+i}
    # In 0-based:
    # w_idx = f_values[idx] % 3 + 1
    # v_idx = w_idx * f_values[N+idx]
    # where idx ranges from 0 to N-1.
    for i in range(N): # i from 0 to N-1
        w_i = f_values[i] % 3 + 1
        v_i = w_i * f_values[N + i] 
        
        if w_i == 1:
            items1_vals.append(v_i)
        elif w_i == 2:
            items2_vals.append(v_i)
        else: # w_i == 3
            items3_vals.append(v_i)

    items1_vals.sort(reverse=True)
    items2_vals.sort(reverse=True)
    items3_vals.sort(reverse=True)

    p1, p2, p3 = 0, 0, 0 # Pointers for items1_vals, items2_vals, items3_vals
    total_value = 0

    len1, len2, len3 = len(items1_vals), len(items2_vals), len(items3_vals)

    for _ in range(K):
        current_options = [] # List of (value_of_this_knapsack_choice, type_tag_for_advancing_pointers)
        
        # Option W3: One item of weight 3
        if p3 < len3:
            current_options.append((items3_vals[p3], "1w3"))
        
        # Option W2+W1: One item of weight 2 and one item of weight 1
        if p2 < len2 and p1 < len1:
            current_options.append((items2_vals[p2] + items1_vals[p1], "1w2_1w1"))

        # Option W1+W1+W1: Three items of weight 1
        if p1 + 2 < len1: # Needs items at p1, p1+1, p1+2
            current_options.append((items1_vals[p1] + items1_vals[p1+1] + items1_vals[p1+2], "3w1"))
            
        # Option W2 (alone): One item of weight 2
        if p2 < len2:
            current_options.append((items2_vals[p2], "1w2"))
            
        # Option W1+W1 (alone): Two items of weight 1
        if p1 + 1 < len1: # Needs items at p1, p1+1
            current_options.append((items1_vals[p1] + items1_vals[p1+1], "2w1"))

        # Option W1 (alone): One item of weight 1
        if p1 < len1:
            current_options.append((items1_vals[p1], "1w1"))

        if not current_options:
            # No more items can be combined to form any knapsack configuration
            break 

        current_options.sort(key=lambda x: x[0], reverse=True)
        
        best_val_for_knapsack, best_type = current_options[0]
        
        total_value += best_val_for_knapsack
        
        if best_type == "1w3":
            p3 += 1
        elif best_type == "1w2_1w1":
            p2 += 1
            p1 += 1
        elif best_type == "3w1":
            p1 += 3
        elif best_type == "1w2":
            p2 += 1
        elif best_type == "2w1":
            p1 += 2
        elif best_type == "1w1":
            p1 += 1
            
    sys.stdout.write(str(total_value) + "\n")

solve()
0