結果
問題 |
No.1560 majority x majority
|
ユーザー |
|
提出日時 | 2022-05-31 09:32:39 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 776 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 82,012 KB |
実行使用メモリ | 105,684 KB |
最終ジャッジ日時 | 2024-09-21 01:09:47 |
合計ジャッジ時間 | 7,361 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 5 |
other | TLE * 1 -- * 25 |
ソースコード
N,M = map(int,input().split()) S = [list(map(int,input().split())) for _ in range(N)] dp = [0] * (1 << M) def calc(mask): l = [0] * N count = 0 for i in range(N): tmp = 1 for j in range(M): if (mask >> j) & 1 == 0:continue tmp &= S[i][j] l[i] = tmp count += tmp return (l,count) for i in range(M): mask = 1 << i l,count = calc(mask) if count >= (N+1) // 2: dp[mask] = 1 for bit in range(1,1 << M): l,count = calc(bit) for i in range(M): mask = 1 << i if mask & bit:continue num = 0 for j in range(N): num += l[j] & S[j][i] if num >= (count + 1) // 2: dp[bit | mask] += dp[bit] print(dp[-1]) #print(dp)