結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    seed = int(data[2])
    a = int(data[3])
    b = int(data[4])
    m = int(data[5])

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

    # Generate items
    list1 = []
    list2 = []
    list3 = []
    for i in range(N):
        w = (f[i] % 3) + 1
        v = w * f[N + i]
        if w == 1:
            list1.append(v)
        elif w == 2:
            list2.append(v)
        else:
            list3.append(v)

    # Sort the lists in descending order
    list1.sort(reverse=True)
    list2.sort(reverse=True)
    list3.sort(reverse=True)

    i3 = 0
    i2 = 0
    i1 = 0
    total = 0
    remaining = K

    while remaining > 0:
        max_val = -1
        best_i3 = i3
        best_i2 = i2
        best_i1 = i1

        # Option 3
        if i3 < len(list3):
            current = list3[i3]
            if current > max_val:
                max_val = current
                best_i3 = i3 + 1
                best_i2 = i2
                best_i1 = i1

        # Option 2+1
        if i2 < len(list2) and i1 < len(list1):
            current = list2[i2] + list1[i1]
            if current > max_val:
                max_val = current
                best_i3 = i3
                best_i2 = i2 + 1
                best_i1 = i1 + 1

        # Option 1+1+1
        if i1 + 2 < len(list1):
            current = list1[i1] + list1[i1 + 1] + list1[i1 + 2]
            if current > max_val:
                max_val = current
                best_i3 = i3
                best_i2 = i2
                best_i1 = i1 + 3

        # Option 2
        if i2 < len(list2):
            current = list2[i2]
            if current > max_val:
                max_val = current
                best_i3 = i3
                best_i2 = i2 + 1
                best_i1 = i1

        # Option 1+1
        if i1 + 1 < len(list1):
            current = list1[i1] + list1[i1 + 1]
            if current > max_val:
                max_val = current
                best_i3 = i3
                best_i2 = i2
                best_i1 = i1 + 2

        # Option 1
        if i1 < len(list1):
            current = list1[i1]
            if current > max_val:
                max_val = current
                best_i3 = i3
                best_i2 = i2
                best_i1 = i1 + 1

        if max_val == -1:
            break  # No more items to choose

        total += max_val
        remaining -= 1
        i3, i2, i1 = best_i3, best_i2, best_i1

    print(total)

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