結果

問題 No.3097 Azuki Kurai
コンテスト
ユーザー RiRinbaru
提出日時 2025-03-26 16:13:22
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 2,099 bytes
コンパイル時間 530 ms
コンパイル使用メモリ 83,040 KB
実行使用メモリ 89,112 KB
最終ジャッジ日時 2025-03-26 16:14:09
合計ジャッジ時間 45,991 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

N_MAX = 10
M_MAX = 2000
bit_N_MAX = 1 << N_MAX

bit = [1 << i for i in range(25)]
sup = 1 << 60

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

def solve1_ac(N, M, K, A, B, ans):
    q = [[[] for _ in range(bit_N_MAX)] for _ in range(N)]
    n = [[0] * bit_N_MAX for _ in range(N)]
    dp = [[0] * bit_N_MAX for _ in range(2)]
    
    for i in range(N):
        for k in range(bit[N]):
            n[i][k] = 0
            kk = k ^ bit[i] if (k & bit[i]) else k
            l = kk
            while l < bit[N]:
                if (l & bit[i]) == 0:
                    for j in range(N):
                        if ((k & bit[(j-1+N) % N]) == 0 and 
                            (k & bit[j]) == 0 and 
                            (k & bit[(j+1) % N]) == 0 and 
                            (l & bit[j]) != 0):
                            break
                    else:
                        q[i][k].append((l, sum(1 for j in range(N) if (k & bit[j]) and 
                                               ((i != (j - 1 + N) % N and (l & bit[(j-1+N) % N]) == 0) or
                                                (i != (j + 1) % N and (l & bit[(j+1) % N]) == 0)))))
                        n[i][k] += 1
                l = (l + 1) | kk
    
    for k in range(bit[N]):
        dp[0][k] = sum(A[j] for j in range(N) if (k & bit[j]) == 0)
    
    cur, prev = 1, 0
    for i in range(1, M+1):
        for k in range(bit[N]):
            dp[cur][k] = sup
        for k in range(bit[N]):
            for l, count in q[B[i]][k]:
                dp[cur][l] = chmin(dp[cur][l], dp[prev][k] + K * count)
        ans[i] = dp[cur][0]
        cur, prev = prev, cur

def main():
    input = sys.stdin.read
    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
    B = [int(data[i]) - 1 for i in range(idx, idx+M)]
    
    ans = [0] * (M+1)
    solve1_ac(N, M, K, A, B, ans)
    
    sys.stdout.write("\n".join(map(str, ans[1:])) + "\n")

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