結果

問題 No.2617 容量3のナップザック
ユーザー gew1fw
提出日時 2025-06-12 21:38:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,718 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 81,984 KB
実行使用メモリ 184,320 KB
最終ジャッジ日時 2025-06-12 21:43:22
合計ジャッジ時間 10,215 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx += 1
    K = int(input[idx]); idx += 1
    seed = int(input[idx]); idx += 1
    a = int(input[idx]); idx += 1
    b = int(input[idx]); idx += 1
    m = int(input[idx]); idx += 1

    f = [0] * (2 * N)
    f[0] = seed
    for i in range(1, 2 * N):
        f[i] = (a * f[i-1] + b) % m

    W1 = []
    W2 = []
    W3 = []

    for i in range(N):
        wi = (f[i] % 3) + 1
        vi = wi * f[N + i]
        if wi == 1:
            W1.append(vi)
        elif wi == 2:
            W2.append(vi)
        else:
            W3.append(vi)

    W1.sort(reverse=True)
    W2.sort(reverse=True)
    W3.sort(reverse=True)

    q1 = deque(W1)
    q2 = deque(W2)
    q3 = deque(W3)

    total = 0

    for _ in range(K):
        option1 = 0
        if q3:
            option1 = q3[0]

        option2 = 0
        if q2 and q1:
            option2 = q2[0] + q1[0]

        option3 = 0
        if len(q1) >= 3:
            option3 = q1[0] + q1[1] + q1[2]

        option4 = 0
        if q1:
            option4 = q1[0]

        max_val = max(option1, option2, option3, option4)

        if max_val == 0:
            break

        if max_val == option1:
            total += option1
            q3.popleft()
        elif max_val == option2:
            total += option2
            q2.popleft()
            q1.popleft()
        elif max_val == option3:
            total += option3
            q1.popleft()
            q1.popleft()
            q1.popleft()
        elif max_val == option4:
            total += option4
            q1.popleft()

    print(total)

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