結果
問題 | No.3097 Azuki Kurai |
ユーザー |
|
提出日時 | 2025-04-05 03:14:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,853 ms / 4,000 ms |
コード長 | 1,570 bytes |
コンパイル時間 | 404 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 87,936 KB |
最終ジャッジ日時 | 2025-04-05 12:57:23 |
合計ジャッジ時間 | 34,933 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
ソースコード
def popcount(x): # 32bit x = x - ((x >> 1) & 0x55555555) x = (x & 0x33333333) + ((x >> 2) & 0x33333333) x = (x + (x >> 4)) & 0x0f0f0f0f x = x + (x >> 8) x = x + (x >> 16) return x & 0x0000007f inf = 10**18 n,m,k = map(int,input().split()) a = list(map(int,input().split())) b = list(map(int,input().split())) dp = [[inf] * (1 << n) for _ in range(m + 1)] for i in range(1 << n): dp[0][i] = 0 for j in range(n): if (i>>j) & 1 == 0: dp[0][i] += a[j] pl = [[] for _ in range(1 << n)] for i in range(1 << n): c = i while c: pl[i].append((popcount(i) - popcount(c)) * k) c = (c - 1) & i pl[i].append((popcount(i)) * k) mae = [[[] for _ in range(1 << n)] for _ in range(n)] for p in range(n): for i in range(1 << n): c = i while c: 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) c = (c - 1) & i now = i now -= (now & (1 << p)) mae[p][i].append(now) for p in range(m): x = b[p] - 1 for i in range(1 << n): f = 0 c = i while c: dp[p+1][mae[x][i][f]] = min(dp[p+1][mae[x][i][f]],dp[p][i]+pl[i][f]) c = (c - 1) & i f += 1 dp[p+1][mae[x][i][f]] = min(dp[p+1][mae[x][i][f]],dp[p][i]+pl[i][f]) for i in range(m): print(dp[i + 1][0])