結果

問題 No.1560 majority x majority
コンテスト
ユーザー tobusakana
提出日時 2022-10-23 14:50:18
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 998 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 238 ms
コンパイル使用メモリ 85,456 KB
実行使用メモリ 654,792 KB
最終ジャッジ日時 2026-03-23 11:57:15
合計ジャッジ時間 12,001 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 MLE * 1
other AC * 24 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

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