結果
問題 |
No.1560 majority x majority
|
ユーザー |
|
提出日時 | 2025-08-30 16:33:46 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,115 bytes |
コンパイル時間 | 351 ms |
コンパイル使用メモリ | 82,036 KB |
実行使用メモリ | 269,196 KB |
最終ジャッジ日時 | 2025-08-30 16:33:54 |
合計ジャッジ時間 | 7,599 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 5 |
other | TLE * 1 -- * 25 |
ソースコード
## https://yukicoder.me/problems/no/1560 def main(): N, M = map(int, input().split()) S = [] for _ in range(N): S.append(list(map(int, input().split()))) bit_map = {} for bit in range(2 ** M): array = [] for i in range(N): is_ok = True for j in range(M): if (1 << j) & bit > 0: if S[i][j] == 0: is_ok = False break if is_ok: array.append(i) bit_map[bit] = array # dp dp = [0] * (2 ** M) dp[0] = 1 for bit in range(2 ** M): if dp[bit] == 0: continue for j in range(M): if (1 << j) & bit == 0: cnt = 0 for y in bit_map[bit]: if S[y][j] == 1: cnt += 1 if cnt >= (len(bit_map[bit]) + 1) // 2: new_bit = bit | (1 << j) dp[new_bit ] += dp[bit] print(dp[2 ** M - 1]) if __name__ == "__main__": main()