結果

問題 No.2617 容量3のナップザック
ユーザー lam6er
提出日時 2025-03-20 20:55:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,548 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 174,432 KB
最終ジャッジ日時 2025-03-20 20:56:13
合計ジャッジ時間 11,311 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    s1 = []
    s2 = []
    s3 = []
    
    for i in range(N):
        # Weight calculation
        wi = (f[i] % 3) + 1
        # Value calculation
        v = wi * f[N + i]
        if wi == 1:
            s1.append(v)
        elif wi == 2:
            s2.append(v)
        else:
            s3.append(v)
    
    # Sort the lists in descending order
    s1.sort(reverse=True)
    s2.sort(reverse=True)
    s3.sort(reverse=True)
    
    len_s1 = len(s1)
    len_s2 = len(s2)
    len_s3 = len(s3)
    
    p1 = 0
    p2 = 0
    p3 = 0
    total = 0
    
    for _ in range(K):
        a_val = s3[p3] if p3 < len_s3 else 0
        b_val = (s2[p2] + s1[p1]) if (p2 < len_s2 and p1 < len_s1) else 0
        c_available = (len_s1 - p1) >= 3
        c_val = sum(s1[p1:p1+3]) if c_available else 0
        d_val = s2[p2] if p2 < len_s2 else 0
        e_available = (len_s1 - p1) >= 2
        e_val = sum(s1[p1:p1+2]) if e_available else 0
        f_val = s1[p1] if p1 < len_s1 else 0
        
        current_max = max(a_val, b_val, c_val, d_val, e_val, f_val)
        if current_max == 0:
            break
        
        # Determine which candidate is chosen (A to F priority)
        selected = None
        if a_val == current_max and p3 < len_s3:
            selected = 'A'
        elif b_val == current_max and p2 < len_s2 and p1 < len_s1:
            selected = 'B'
        elif c_val == current_max and c_available:
            selected = 'C'
        elif d_val == current_max and p2 < len_s2:
            selected = 'D'
        elif e_val == current_max and e_available:
            selected = 'E'
        elif f_val == current_max and p1 < len_s1:
            selected = 'F'
        else:
            break  # no candidates available (shouldn't happen)
        
        # Update total and pointers
        total += current_max
        if selected == 'A':
            p3 += 1
        elif selected == 'B':
            p2 += 1
            p1 += 1
        elif selected == 'C':
            p1 += 3
        elif selected == 'D':
            p2 += 1
        elif selected == 'E':
            p1 += 2
        elif selected == 'F':
            p1 += 1
    
    print(total)

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