結果

問題 No.2617 容量3のナップザック
ユーザー qwewe
提出日時 2025-05-14 12:53:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,981 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 161,024 KB
最終ジャッジ日時 2025-05-14 12:55:17
合計ジャッジ時間 8,930 ms
ジャッジサーバーID
（参考情報） 		judge5 / 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 items
    s1 = []
    s2 = []
    s3 = []
    for i in range(N):
        fi = f[i]
        w = (fi % 3) + 1
        v = w * f[N + i]
        if w == 1:
            s1.append(v)
        elif w == 2:
            s2.append(v)
        else:
            s3.append(v)
    
    # Sort each list in descending order
    s1.sort(reverse=True)
    s2.sort(reverse=True)
    s3.sort(reverse=True)
    
    i1 = i2 = i3 = 0
    len_s1 = len(s1)
    len_s2 = len(s2)
    len_s3 = len(s3)
    total = 0
    
    for _ in range(K):
        max_val = -1
        opt = -1
        
        # Check all possible options and select the maximum
        # Option a: s3[i3]
        if i3 < len_s3:
            current = s3[i3]
            if current > max_val:
                max_val = current
                opt = 1
        
        # Option b: s2[i2] + s1[i1]
        if i2 < len_s2 and i1 < len_s1:
            current = s2[i2] + s1[i1]
            if current > max_val:
                max_val = current
                opt = 2
        
        # Option c: s1[i1] + s1[i1+1] + s1[i1+2]
        if i1 + 2 < len_s1:
            current = s1[i1] + s1[i1+1] + s1[i1+2]
            if current > max_val:
                max_val = current
                opt = 3
        
        # Option d: s2[i2]
        if i2 < len_s2 and opt == -1:
            current = s2[i2]
            if current > max_val:
                max_val = current
                opt = 4
        elif i2 < len_s2:
            current = s2[i2]
            if current > max_val:
                max_val = current
                opt = 4
        
        # Option e: s1[i1] + s1[i1+1]
        if i1 + 1 < len_s1:
            current = s1[i1] + s1[i1+1]
            if current > max_val:
                max_val = current
                opt = 5
        
        # Option f: s1[i1]
        if i1 < len_s1 and opt == -1:
            current = s1[i1]
            if current > max_val:
                max_val = current
                opt = 6
        elif i1 < len_s1:
            current = s1[i1]
            if current > max_val:
                max_val = current
                opt = 6
        
        if opt == -1:
            break  # no more items
        
        total += max_val
        
        # Update indices based on the selected option
        if opt == 1:
            i3 += 1
        elif opt == 2:
            i2 += 1
            i1 += 1
        elif opt == 3:
            i1 += 3
        elif opt == 4:
            i2 += 1
        elif opt == 5:
            i1 += 2
        elif opt == 6:
            i1 += 1
    
    print(total)

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