結果
問題 |
No.1560 majority x majority
|
ユーザー |
|
提出日時 | 2025-08-30 16:46:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,336 ms / 2,000 ms |
コード長 | 1,097 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 252,320 KB |
最終ジャッジ日時 | 2025-08-30 16:47:08 |
合計ジャッジ時間 | 9,422 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 26 |
ソースコード
## 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()))) n_bts = [] for i in range(N): bit = 0 for j in range(M): if S[i][j] == 1: bit |= (1 << j) n_bts.append(bit) bit_map = {} for bit in range(2 ** M): array = [] for i in range(N): if n_bts[i] & bit == bit: 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 new_bit = bit | (1 << j) for y in bit_map[bit]: if S[y][j] == 1: cnt += 1 if cnt >= (len(bit_map[bit]) + 1) // 2: dp[new_bit ] += dp[bit] print(dp[2 ** M - 1]) if __name__ == "__main__": main()