結果
問題 | No.753 最強王者決定戦 |
ユーザー | maspy |
提出日時 | 2020-03-28 02:14:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 789 ms / 1,000 ms |
コード長 | 1,229 bytes |
コンパイル時間 | 413 ms |
コンパイル使用メモリ | 87,096 KB |
実行使用メモリ | 92,844 KB |
最終ジャッジ日時 | 2023-08-30 17:17:48 |
合計ジャッジ時間 | 5,004 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 776 ms
92,616 KB |
testcase_01 | AC | 771 ms
92,728 KB |
testcase_02 | AC | 774 ms
92,592 KB |
testcase_03 | AC | 789 ms
92,844 KB |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import itertools A = list(map(int, read().split())) for l in range(16): for r in range(l): A[16 * l + r] = -A[16 * r + l] dp = [[0] * 16 for _ in range(1 << 16)] for n in range(16): dp[1 << n][n] = 1 popcount = [0] for _ in range(16): popcount += [x + 1 for x in popcount] for size in [2, 4, 8, 16]: for n in range(1 << 16): if popcount[n] != size: continue I = [i for i in range(16) if n & (1 << i)] for L in itertools.combinations(I, size // 2): L = sum(1 << i for i in L) R = n - L if L > R: continue for l in range(16): if not (L & (1 << l)): continue for r in range(16): if not (R & (1 << r)): continue x = dp[L][l] * dp[R][r] if A[16 * l + r] == 1: dp[n][l] += x else: dp[n][r] += x answer = [x << 15 for x in dp[-1]] print('\n'.join(map(str, answer)))