結果

問題 No.2617 容量3のナップザック
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:58:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,798 bytes
コンパイル時間 290 ms
コンパイル使用メモリ 82,000 KB
実行使用メモリ 181,500 KB
最終ジャッジ日時 2025-06-12 16:59:00
合計ジャッジ時間 9,667 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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):
        fi = f[i]
        w = (fi % 3) + 1
        v = w * f[N + i]
        if w == 1:
            w1.append(v)
        elif w == 2:
            w2.append(v)
        else:
            w3.append(v)
    
    w1.sort(reverse=True)
    w2.sort(reverse=True)
    w3.sort(reverse=True)
    
    prefix_w1 = [0] * (len(w1) + 1)
    for i in range(len(w1)):
        prefix_w1[i+1] = prefix_w1[i] + w1[i]
    
    i1 = 0
    i2 = 0
    i3 = 0
    total = 0
    
    for _ in range(K):
        a_val = None
        b_val = None
        c_val = None
        
        if i3 < len(w3):
            a_val = w3[i3]
        
        if i2 < len(w2) and i1 < len(w1):
            b_val = w2[i2] + w1[i1]
        
        if i1 + 2 < len(w1):
            c_val = prefix_w1[i1 + 3] - prefix_w1[i1]
        
        options = []
        if a_val is not None:
            options.append((a_val, 'a'))
        if b_val is not None:
            options.append((b_val, 'b'))
        if c_val is not None:
            options.append((c_val, 'c'))
        
        if not options:
            break
        
        max_val, max_type = max(options, key=lambda x: x[0])
        total += max_val
        
        if max_type == 'a':
            i3 += 1
        elif max_type == 'b':
            i2 += 1
            i1 += 1
        elif max_type == 'c':
            i1 += 3
    
    print(total)

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