結果
問題 | No.943 取り調べ |
ユーザー |
![]() |
提出日時 | 2019-12-06 20:06:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 549 ms / 1,206 ms |
コード長 | 839 bytes |
コンパイル時間 | 360 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 77,996 KB |
最終ジャッジ日時 | 2024-12-23 16:15:59 |
合計ジャッジ時間 | 4,417 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
N = int(input()) X = [tuple(map(int,input().split())) for i in range(N)] A = list(map(int,input().split())) oks = set() visited = set() def isok(b,i): if i in oks: return True if i in visited: return False visited.add(i) for j,x in enumerate(X[i]): if x==0 or b&(1<<j): continue if isok(b,j): continue return False oks.add(i) return True ans = sum(A) for b in range(1<<N): tmp = 0 for i in range(N): if b&(1<<i): tmp += A[i] if tmp >= ans: continue oks = set() for i,row in enumerate(X): for j in range(N): if row[j] and b&(1<<j)==0:break else: oks.add(i) visited = set() for i in range(N): if i in oks: continue if isok(b,i): continue break else: ans = tmp print(ans)