結果
問題 |
No.943 取り調べ
|
ユーザー |
![]() |
提出日時 | 2020-02-21 17:52:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 525 ms / 1,206 ms |
コード長 | 824 bytes |
コンパイル時間 | 361 ms |
コンパイル使用メモリ | 82,068 KB |
実行使用メモリ | 78,184 KB |
最終ジャッジ日時 | 2024-10-08 19:54:20 |
合計ジャッジ時間 | 4,651 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
N = int(input()) X = [[int(x) for x in input().split()] for _ in range(N)] A = [int(a) for a in input().split()] par = [set([]) for _ in range(N)] for i in range(N): for j in range(N): if X[i][j] == 1: par[i].add(j) dp = [-1]*(2**N) dp[-1] = 1 def f(n): if dp[n] >= 0: return dp[n] S = set([]) for j in range(N): if n & (1<<j): S.add(j) for i in range(N): if par[i] <= S: S.add(i) m = 0 for j in range(N): if j in S: m += 1<<j if m == n: dp[n] = 0 else: dp[n] = f(m) return dp[n] ans = sum(A) for i in range(2**N-1, -1, -1): if f(i) <= 0: continue cnt = 0 for j in range(N): if i & (1<<j): cnt += A[j] ans = min(ans, cnt) print(ans)