結果
| 問題 | No.1560 majority x majority |
| ユーザー |
 tobusakana
|
| 提出日時 | 2022-10-23 14:50:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 998 bytes |
| コンパイル時間 | 259 ms |
| コンパイル使用メモリ | 87,176 KB |
| 実行使用メモリ | 500,400 KB |
| 最終ジャッジ日時 | 2023-09-15 01:10:42 |
| 合計ジャッジ時間 | 7,108 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| 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 | -- | - |
ソースコード
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])