結果

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

ソースコード

diff # 

def main():
    import sys
    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

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

    # Separate into w3, w2, w1
    w3 = []
    w2 = []
    w1 = []
    for i in range(N):
        fi = f[i]
        w = (fi % 3) + 1
        v = w * f[i + N]
        if w == 3:
            w3.append(v)
        elif w == 2:
            w2.append(v)
        else:
            w1.append(v)

    # Sort each in descending order
    w3.sort(reverse=True)
    w2.sort(reverse=True)
    w1.sort(reverse=True)

    i3 = 0
    i2 = 0
    i1 = 0
    total = 0
    groups_formed = 0

    while groups_formed < K:
        possible = []

        # Check group3
        if i3 < len(w3):
            possible.append((w3[i3], 'group3'))

        # Check group2_1
        if i2 < len(w2) and i1 < len(w1):
            possible.append((w2[i2] + w1[i1], 'group2_1'))

        # Check group1 options
        max_take = min(3, len(w1) - i1)
        if max_take >= 3:
            sum_v = w1[i1] + w1[i1 + 1] + w1[i1 + 2]
            possible.append((sum_v, 'group1_3'))
        elif max_take >= 2:
            sum_v = w1[i1] + w1[i1 + 1]
            possible.append((sum_v, 'group1_2'))
        elif max_take >= 1:
            possible.append((w1[i1], 'group1_1'))

        if not possible:
            break

        # Select the maximum value option
        max_val = -1
        selected = None
        for val, typ in possible:
            if val > max_val:
                max_val = val
                selected = typ

        if selected is None:
            break

        # Form the group
        if selected == 'group3':
            total += w3[i3]
            i3 += 1
        elif selected == 'group2_1':
            total += w2[i2] + w1[i1]
            i2 += 1
            i1 += 1
        elif selected == 'group1_3':
            total += w1[i1] + w1[i1 + 1] + w1[i1 + 2]
            i1 += 3
        elif selected == 'group1_2':
            total += w1[i1] + w1[i1 + 1]
            i1 += 2
        elif selected == 'group1_1':
            total += w1[i1]
            i1 += 1

        groups_formed += 1

    print(total)

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