結果

問題 No.2617 容量3のナップザック
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:36:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,437 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 184,552 KB
最終ジャッジ日時 2025-06-12 21:38:39
合計ジャッジ時間 11,960 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K, seed, a, b, m = map(int, sys.stdin.readline().split())
    
    # Generate f sequence of 2N elements
    f = [0] * (2 * N)
    f[0] = seed % m  # Ensure it's within mod m
    for i in range(1, 2 * N):
        f[i] = (a * f[i-1] + b) % m
    
    # Group items into A, B, C based on weight, then sort each in descending order of value
    A = []
    B = []
    C = []
    for i in range(N):
        f_i = f[i]
        w = (f_i % 3) + 1
        v = w * f[N + i]
        if w == 1:
            A.append(v)
        elif w == 2:
            B.append(v)
        else:
            C.append(v)
    
    # Sort each group in descending order
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    
    # Convert to deques for efficient popping from front
    A = deque(A)
    B = deque(B)
    C = deque(C)
    
    total = 0
    while K > 0 and (A or B or C):
        max_val = -1
        selected = None
        
        # Option a: take C[0]
        if C and C[0] > max_val:
            max_val = C[0]
            selected = 'a'
        
        # Option b: B[0] + A[0]
        if B and A and (B[0] + A[0]) > max_val:
            max_val = B[0] + A[0]
            selected = 'b'
        
        # Option c: A[0] + A[1]
        if len(A) >= 2 and (A[0] + A[1]) > max_val:
            max_val = A[0] + A[1]
            selected = 'c'
        
        # Option d: A[0] + A[1] + A[2]
        if len(A) >= 3 and (A[0] + A[1] + A[2]) > max_val:
            max_val = A[0] + A[1] + A[2]
            selected = 'd'
        
        # Option e: B[0]
        if B and B[0] > max_val:
            max_val = B[0]
            selected = 'e'
        
        # Option f: A[0]
        if A and A[0] > max_val:
            max_val = A[0]
            selected = 'f'
        
        if selected is None:
            break  # No more items to take
        
        if selected == 'a':
            total += C.popleft()
        elif selected == 'b':
            total += B.popleft() + A.popleft()
        elif selected == 'c':
            total += A.popleft() + A.popleft()
        elif selected == 'd':
            total += A.popleft() + A.popleft() + A.popleft()
        elif selected == 'e':
            total += B.popleft()
        elif selected == 'f':
            total += A.popleft()
        
        K -= 1
    
    print(total)

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