結果

問題 No.2617 容量3のナップザック
ユーザー qwewe
提出日時 2025-05-14 12:51:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,580 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,216 KB
実行使用メモリ 162,292 KB
最終ジャッジ日時 2025-05-14 12:53:19
合計ジャッジ時間 9,246 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    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)

    # Sort each weight group in descending order
    w1.sort(reverse=True)
    w2.sort(reverse=True)
    w3.sort(reverse=True)

    len1, len2, len3 = len(w1), len(w2), len(w3)
    i1 = i2 = i3 = 0
    total = 0
    remaining = K

    while remaining > 0:
        max_val = 0
        selected = None

        # Check all possible candidates
        # Candidate A: weight 3
        if i3 < len3:
            val = w3[i3]
            if val > max_val:
                max_val = val
                selected = 'A'

        # Candidate B: weight 2 + 1
        if i2 < len2 and i1 < len1:
            val = w2[i2] + w1[i1]
            if val > max_val:
                max_val = val
                selected = 'B'

        # Candidate C: weight 1+1+1
        if i1 + 2 < len1:
            val = w1[i1] + w1[i1+1] + w1[i1+2]
            if val > max_val:
                max_val = val
                selected = 'C'

        # Candidate D: weight 1+1
        if i1 + 1 < len1:
            val = w1[i1] + w1[i1+1]
            if val > max_val:
                max_val = val
                selected = 'D'

        # Candidate E: weight 1
        if i1 < len1:
            val = w1[i1]
            if val > max_val:
                max_val = val
                selected = 'E'

        # Candidate F: weight 2
        if i2 < len2:
            val = w2[i2]
            if val > max_val:
                max_val = val
                selected = 'F'

        if selected is None:
            break  # No more items

        total += max_val
        remaining -= 1

        # Update indices based on selected candidate
        if selected == 'A':
            i3 += 1
        elif selected == 'B':
            i2 += 1
            i1 += 1
        elif selected == 'C':
            i1 += 3
        elif selected == 'D':
            i1 += 2
        elif selected == 'E':
            i1 += 1
        elif selected == 'F':
            i2 += 1

    print(total)

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