結果
問題 |
No.943 取り調べ
|
ユーザー |
![]() |
提出日時 | 2020-02-29 01:26:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 106 ms / 1,206 ms |
コード長 | 900 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 82,332 KB |
実行使用メモリ | 80,128 KB |
最終ジャッジ日時 | 2024-10-13 19:39:57 |
合計ジャッジ時間 | 2,714 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#!/usr/bin/env python3 # %% import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines # %% N = int(readline()) XA = tuple(map(int, read().split())) X = XA[:N * N] A = XA[N * N:] # %% need_subset = [0] * N for i in range(N): need_subset[i] = sum((1 << j) * x for j, x in enumerate(X[N * i:N * i + N])) # %% dp = list(range(1 << N)) full = (1 << N) - 1 for n in range(full, -1, -1): for i in range(N): if n & (1 << i): continue if n & need_subset[i] == need_subset[i]: dp[n] = dp[n ^ (1 << i)] break # %% cost = [0] * (1 << N) for n in range(1, 1 << N): m = n & (-n) cost[n] = cost[n ^ m] + A[m.bit_length() - 1] # %% answer = cost[full] for n in range(1 << N): if dp[n] == full: x = cost[n] if answer > x: answer = x # %% print(answer)