結果

問題 No.2617 容量3のナップザック
ユーザー qwewe
提出日時 2025-04-24 12:28:24
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,990 bytes
コンパイル時間 219 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 160,896 KB
最終ジャッジ日時 2025-04-24 12:30:35
合計ジャッジ時間 10,770 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 array (1-based to 2N)
    f = [0] * (2 * N)
    f[0] = seed
    for i in range(1, 2 * N):
        f[i] = (a * f[i-1] + b) % m

    # Generate items
    w1 = []
    w2 = []
    w3 = []
    for i in range(N):
        fi = f[i]
        wi = (fi % 3) + 1
        v_i = wi * f[N + i]
        if wi == 1:
            w1.append(v_i)
        elif wi == 2:
            w2.append(v_i)
        else:
            w3.append(v_i)

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

    i1 = 0
    i2 = 0
    i3 = 0
    sum_val = 0
    remaining = K

    len_w1 = len(w1)
    len_w2 = len(w2)
    len_w3 = len(w3)

    while remaining > 0:
        max_val = 0
        choice = None

        # Check candidate A (w3)
        if i3 < len_w3:
            current_a = w3[i3]
            if current_a > max_val:
                max_val = current_a
                choice = 'A'

        # Check candidate B (w2 + w1)
        if i2 < len_w2 and i1 < len_w1:
            current_b = w2[i2] + w1[i1]
            if current_b > max_val:
                max_val = current_b
                choice = 'B'

        # Check candidate C (w1 *3)
        if i1 + 2 < len_w1:
            current_c = w1[i1] + w1[i1+1] + w1[i1+2]
            if current_c > max_val:
                max_val = current_c
                choice = 'C'

        if choice is None:
            break  # No more candidates

        sum_val += max_val
        remaining -= 1

        if choice == 'A':
            i3 += 1
        elif choice == 'B':
            i2 += 1
            i1 += 1
        elif choice == 'C':
            i1 += 3

    print(sum_val)

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