結果

問題 No.1560 majority x majority
ユーザー tobusakanatobusakana
提出日時 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
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

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