結果

問題 No.3097 Azuki Kurai
コンテスト
ユーザー RiRinbaru
提出日時 2025-03-29 04:52:52
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,684 bytes
コンパイル時間 408 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 92,712 KB
最終ジャッジ日時 2025-03-29 04:52:59
合計ジャッジ時間 5,272 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

input = sys.stdin.read

def chmin(a, b):
    return min(a, b)

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    M = int(data[idx + 1])
    K = int(data[idx + 2])
    idx += 3
    
    A = list(map(int, data[idx:idx + N]))
    idx += N
    
    linf = float('inf')
    dp = [[linf] * (1 << N) for _ in range(M + 1)]
    
    for i in range(1 << N):
        dp[0][i] = sum(A[j] for j in range(N) if not (i & (1 << j)))
    
    popcount = [bin(i).count('1') for i in range(1 << N)]
    pl = [[(popcount[i] - popcount[c]) * K for c in range(i, 0, -1 & i)] + [(popcount[i] - popcount[0]) * K] for i in range(1 << N)]
    
    mae = [[[] for _ in range(1 << N)] for _ in range(N)]
    
    for p in range(N):
        for i in range(1 << N):
            for c in range(i, 0, -1 & i):
                now = i
                now |= ((c * 2) - ((c * 2) & (1 << N)))
                now |= (((c * 2) & (1 << N)) >> N)
                now |= (c // 2)
                now |= (c % 2) * (1 << (N - 1))
                now -= (now & (1 << p))
                mae[p][i].append(now)
            now = i
            now -= (now & (1 << p))
            mae[p][i].append(now)
    
    for p in range(M):
        B = int(data[idx]) - 1
        idx += 1
        
        for i in range(1 << N):
            F = 0
            for c in range(i, 0, -1 & i):
                dp[p + 1][mae[B][i][F]] = chmin(dp[p + 1][mae[B][i][F]], dp[p][i] + pl[i][F])
                F += 1
            dp[p + 1][mae[B][i][F]] = chmin(dp[p + 1][mae[B][i][F]], dp[p][i] + pl[i][F])
    
    for i in range(1, M + 1):
        print(dp[i][0])

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