結果

問題 No.1560 majority x majority
コンテスト
ユーザー tobusakana
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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])
0