結果

問題 No.2617 容量3のナップザック
ユーザー gew1fw
提出日時 2025-06-12 21:38:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,569 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 169,368 KB
最終ジャッジ日時 2025-06-12 21:43:31
合計ジャッジ時間 10,533 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys

    N, K, seed, a, b, m = map(int, sys.stdin.readline().split())

    # Compute f_1 to f_2N
    f = [0] * (2 * N + 2)  # 1-based indexing up to 2N
    f[1] = seed
    for i in range(1, 2 * N):
        f[i + 1] = (a * f[i] + b) % m

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

    # Sort the groups in descending order
    W1.sort(reverse=True)
    W2.sort(reverse=True)
    W3.sort(reverse=True)

    # Compute prefix sums for W1
    prefix_sum = [0] * (len(W1) + 1)
    for i in range(len(W1)):
        prefix_sum[i + 1] = prefix_sum[i] + W1[i]

    # Initialize pointers
    i1 = 0
    i2 = 0
    i3 = 0
    total = 0

    for _ in range(K):
        max_val = -1
        best_config = None  # (di1, di2, di3)

        # Check Type C: 3 W1 items
        if i1 + 3 <= len(W1):
            current_val = prefix_sum[i1 + 3] - prefix_sum[i1]
            if current_val > max_val:
                max_val = current_val
                best_config = (3, 0, 0)

        # Check Type B: 1 W2 and 1 W1
        if i2 < len(W2) and i1 < len(W1):
            current_val = W2[i2] + W1[i1]
            if current_val > max_val:
                max_val = current_val
                best_config = (1, 1, 0)

        # Check Type A: 1 W3
        if i3 < len(W3):
            current_val = W3[i3]
            if current_val > max_val:
                max_val = current_val
                best_config = (0, 0, 1)

        # Check Type D: 2 W1 items
        if i1 + 2 <= len(W1):
            current_val = W1[i1] + W1[i1 + 1]
            if current_val > max_val:
                max_val = current_val
                best_config = (2, 0, 0)

        # Check Type E: 1 W1
        if i1 < len(W1):
            current_val = W1[i1]
            if current_val > max_val:
                max_val = current_val
                best_config = (1, 0, 0)

        # Check Type F: 1 W2
        if i2 < len(W2):
            current_val = W2[i2]
            if current_val > max_val:
                max_val = current_val
                best_config = (0, 1, 0)

        if best_config is not None:
            total += max_val
            di1, di2, di3 = best_config
            i1 += di1
            i2 += di2
            i3 += di3

    print(total)

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