結果

問題 No.2617 容量3のナップザック
ユーザー gew1fw
提出日時 2025-06-12 16:58:26
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,303 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 173,892 KB
最終ジャッジ日時 2025-06-12 16:58:54
合計ジャッジ時間 10,988 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    K = int(input[idx]); idx +=1
    seed = int(input[idx]); idx +=1
    a = int(input[idx]); idx +=1
    b = int(input[idx]); idx +=1
    m = int(input[idx]); idx +=1

    # Generate f sequence
    f = [0] * (2 * N)
    f[0] = seed
    for i in range(1, 2 * N):
        f[i] = (a * f[i-1] + b) % m

    # Split into G1, G2, G3
    G1 = []
    G2 = []
    G3 = []
    for i in range(N):
        wi = f[i] % 3 + 1
        vi = wi * f[N + i]
        if wi == 1:
            G1.append(vi)
        elif wi == 2:
            G2.append(vi)
        else:
            G3.append(vi)

    # Sort each group in descending order
    G1.sort(reverse=True)
    G2.sort(reverse=True)
    G3.sort(reverse=True)

    i = 0  # pointer for G3
    j = 0  # pointer for G2
    k = 0  # pointer for G1
    total = 0

    for _ in range(K):
        candidates = []
        # Configuration 1: G3
        if i < len(G3):
            candidates.append( (G3[i], 1) )
        # Configuration 2: G2
        if j < len(G2):
            candidates.append( (G2[j], 2) )
        # Configuration3: G1
        if k < len(G1):
            candidates.append( (G1[k], 3) )
        # Configuration4: G2 + G1
        if j < len(G2) and k < len(G1):
            val = G2[j] + G1[k]
            candidates.append( (val, 4) )
        # Configuration5: G1 + G1
        if k + 1 < len(G1):
            val = G1[k] + G1[k+1]
            candidates.append( (val, 5) )
        # Configuration6: G1 + G1 + G1
        if k + 2 < len(G1):
            val = G1[k] + G1[k+1] + G1[k+2]
            candidates.append( (val, 6) )
        
        if not candidates:
            break
        
        # Find the maximum value configuration
        max_val = max(candidates, key=lambda x: x[0])
        val, config = max_val
        total += val
        
        # Update pointers based on the configuration
        if config == 1:
            i += 1
        elif config == 2:
            j += 1
        elif config == 3:
            k += 1
        elif config == 4:
            j += 1
            k += 1
        elif config == 5:
            k += 2
        elif config == 6:
            k += 3

    print(total)

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