結果

問題 No.3097 Azuki Kurai
ユーザー RiRinbaru
提出日時 2025-03-23 07:37:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,221 bytes
コンパイル時間 626 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 107,952 KB
最終ジャッジ日時 2025-03-23 07:37:31
合計ジャッジ時間 19,136 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import product

def chmin(a, b):
    return b if a > b else a

def main():
    input = sys.stdin.read
    data = input().split()
    index = 0
    
    N, M, K = map(int, data[index:index+3])
    index += 3
    A = list(map(int, data[index:index+N]))
    index += N
    
    linf = 4 * 10**18
    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)))
    
    for p in range(M):
        B = int(data[index]) - 1
        index += 1
        
        for i in range(1 << N):
            c = i
            while c:
                now, temp = i, dp[p][i]
                temp += (bin(i).count('1') - bin(c).count('1')) * K
                now |= ((c << 1) & ((1 << N) - 1))
                now |= (c >> 1)
                now &= ~(1 << B)
                dp[p + 1][now] = chmin(dp[p + 1][now], temp)
                c = (c - 1) & i
            
            now, temp = i, dp[p][i]
            temp += bin(i).count('1') * K
            now &= ~(1 << B)
            dp[p + 1][now] = chmin(dp[p + 1][now], temp)
    
    for i in range(M):
        print(dp[i + 1][0])

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