結果

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

ソースコード

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])
    
    f = [0] * (2 * N)
    f[0] = seed
    for i in range(1, 2 * N):
        f[i] = (a * f[i-1] + b) % m
    
    w1 = []
    w2 = []
    w3 = []
    for i in range(N):
        wi = (f[i] % 3) + 1
        vi = wi * f[N + i]
        if wi == 1:
            w1.append(vi)
        elif wi == 2:
            w2.append(vi)
        else:
            w3.append(vi)
    
    w1.sort(reverse=True)
    w2.sort(reverse=True)
    w3.sort(reverse=True)
    
    pre_sum_w1 = [0] * (len(w1) + 1)
    for i in range(len(w1)):
        pre_sum_w1[i+1] = pre_sum_w1[i] + w1[i]
    
    i3 = 0
    i2 = 0
    i1 = 0
    total = 0
    remaining = K
    
    while remaining > 0:
        options = []
        if i3 < len(w3):
            options.append((w3[i3], '3'))
        if i2 < len(w2) and i1 < len(w1):
            options.append((w2[i2] + w1[i1], '21'))
        if i1 + 3 <= len(w1):
            val = pre_sum_w1[i1 + 3] - pre_sum_w1[i1]
            options.append((val, '111'))
        if not options:
            break
        
        max_option = max(options, key=lambda x: x[0])
        if max_option[1] == '3':
            total += max_option[0]
            i3 += 1
        elif max_option[1] == '21':
            total += max_option[0]
            i2 += 1
            i1 += 1
        else:
            total += max_option[0]
            i1 += 3
        
        remaining -= 1
    
    print(total)

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