結果
問題 |
No.1560 majority x majority
|
ユーザー |
|
提出日時 | 2022-10-23 14:50:18 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 998 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 924,996 KB |
最終ジャッジ日時 | 2024-07-02 07:02:15 |
合計ジャッジ時間 | 6,758 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 5 |
other | MLE * 1 -- * 25 |
ソースコード
import sys readline = sys.stdin.readline N,M = map(int,readline().split()) S = [list(map(int,readline().split())) for i in range(N)] survive = [set() for i in range(1 << M)] # survive[S] = 状態Sのときに残っている人のindex for i in range(N): survive[0].add(i) # 状態0のときは全員残っている dp = [0] * (1 << M) dp[0] = 1 for status in range(1 << M): for target in range(M): # 次に議論したい議題の選択 if (status >> target) & 1: # 議論済み continue # targetを可決できるか。 total_member = len(survive[status]) # 現在残っているメンバ limit = (total_member + 1) // 2 # 獲得すべき票数(以上) next_status = status | (1 << target) vote = 0 voter = set() for s in survive[status]: if S[s][target] == 1: # 賛成である vote += 1 voter.add(s) if vote >= limit: # 可決 survive[next_status] |= voter dp[next_status] += dp[status] print(dp[-1])