結果

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

ソースコード

diff # 

import sys
from itertools import product

sys.setrecursionlimit(10**6)
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 = 4 * 10**18
    dp = [[linf] * (1 << N) for _ in range(M + 1)]
    
    for i in range(1 << N):
        dp[0][i] = 0
        for j in range(N):
            if not (i & (1 << j)):
                dp[0][i] += A[j]
    
    pl = [[] for _ in range(1 << N)]
    for i in range(1 << N):
        for c in range(i, 0, -1 & i):
            pl[i].append((bin(i).count('1') - bin(c).count('1')) * K)
        pl[i].append((bin(i).count('1') - bin(0).count('1')) * K)
    
    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