結果

問題 No.2617 容量3のナップザック
ユーザー qwewe
提出日時 2025-04-24 12:28:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,446 bytes
コンパイル時間 196 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 251,800 KB
最終ジャッジ日時 2025-04-24 12:30:50
合計ジャッジ時間 12,545 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    # Generate 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 w and v lists
    w_list = []
    v_list = []
    for i in range(N):
        wi = (f[i] % 3) + 1
        vi = wi * f[N + i]
        w_list.append(wi)
        v_list.append(vi)

    # Separate into weight categories and sort
    w1 = []
    w2 = []
    w3 = []
    for i in range(N):
        if w_list[i] == 1:
            w1.append(v_list[i])
        elif w_list[i] == 2:
            w2.append(v_list[i])
        else:
            w3.append(v_list[i])
    w1.sort(reverse=True)
    w2.sort(reverse=True)
    w3.sort(reverse=True)

    current_w1 = 0
    current_w2 = 0
    current_w3 = 0
    total = 0

    for _ in range(K):
        candidates = []

        # Check each possible candidate
        # a: w3 single
        if current_w3 < len(w3):
            candidates.append((w3[current_w3], 'a'))
        # b: w2 + w1
        if current_w2 < len(w2) and current_w1 < len(w1):
            candidates.append((w2[current_w2] + w1[current_w1], 'b'))
        # c: w1*3
        if current_w1 + 2 < len(w1):
            sum_c = w1[current_w1] + w1[current_w1+1] + w1[current_w1+2]
            candidates.append((sum_c, 'c'))
        # d: w2 single
        if current_w2 < len(w2):
            candidates.append((w2[current_w2], 'd'))
        # e: w1*2
        if current_w1 + 1 < len(w1):
            sum_e = w1[current_w1] + w1[current_w1+1]
            candidates.append((sum_e, 'e'))
        # f: w1 single
        if current_w1 < len(w1):
            candidates.append((w1[current_w1], 'f'))

        if not candidates:
            break

        # Select the maximum candidate
        max_val, type_ = max(candidates, key=lambda x: x[0])
        total += max_val

        # Update pointers
        if type_ == 'a':
            current_w3 += 1
        elif type_ == 'b':
            current_w2 += 1
            current_w1 += 1
        elif type_ == 'c':
            current_w1 += 3
        elif type_ == 'd':
            current_w2 += 1
        elif type_ == 'e':
            current_w1 += 2
        elif type_ == 'f':
            current_w1 += 1

    print(total)

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