結果

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

ソースコード

diff # 

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

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

    # Group items
    W1 = []
    W2 = []
    W3 = []

    for i in range(N):
        current_f = f[i]
        w = (current_f % 3) + 1
        v = w * f[N + i]

        if w == 1:
            W1.append(v)
        elif w == 2:
            W2.append(v)
        else:
            W3.append(v)

    # Sort each group in descending order
    W1.sort(reverse=True)
    W2.sort(reverse=True)
    W3.sort(reverse=True)

    # Initialize pointers
    ptr1 = 0
    ptr2 = 0
    ptr3 = 0

    total = 0

    for _ in range(K):
        max_val = -1
        option = None

        # Option a: take from W3
        if ptr3 < len(W3):
            val = W3[ptr3]
            if val > max_val:
                max_val = val
                option = 'a'

        # Option b: take from W2 and W1
        if ptr2 < len(W2) and ptr1 < len(W1):
            val = W2[ptr2] + W1[ptr1]
            if val > max_val:
                max_val = val
                option = 'b'

        # Option c: take three from W1
        if ptr1 + 2 < len(W1):
            val = W1[ptr1] + W1[ptr1 +1] + W1[ptr1 +2]
            if val > max_val:
                max_val = val
                option = 'c'

        if option is None:
            break

        total += max_val

        # Update pointers
        if option == 'a':
            ptr3 += 1
        elif option == 'b':
            ptr2 += 1
            ptr1 += 1
        elif option == 'c':
            ptr1 += 3

    print(total)

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