P9333 [JOISC 2023] Council (Day2)
题目描述
#### 题目翻译
在 JOI 市议会中,有 $N$ 名议员,编号从 $1$ 到 $N$。议会将召开会议,议员们将对 $M$ 项提案进行表决,编号为 $1$ 到 $M$。如果 $A_{i,j}=1$,则议员 $i (1≤i≤N)$ 将对提案 $j (1≤j≤M)$ 表决肯定票。如果 $A_{i,j}=0$,则议员 $i$ 将对提案 $j$ 表决否定票。
JOI 市议会的程序如下所示。
+ 在 $N$ 名议员中,通过抽签随机选择主席。
+ 主席将在除了主席以外的其他 $N−1$ 名议员中选择副主席。
+ 将对 $M$ 项提案进行表决。除了主席和副主席以外的其他 $N−2$ 名议员,每人对每个提案均投票支持或反对。如果大多数议员(即肯定票大于等于 $⌊\dfrac{N}{2}⌋$)投票赞成,则议会将批准该提案。其中 $⌊x⌋$ 表示不超过 $x$ 的最大整数。
市长 K 希望议会尽可能地批准更多的提案。市长 K 收集了议员的信息并知道每个议员在每个提案上的表决结果。
请编写程序,在给定议员投票信息的情况下,计算每个议员作为主席时议会可以批准的提案数量的最大可能值。
输入格式
无
输出格式
无
说明/提示
**【样例解释 #1】**
- Let’s consider the case where the assembly member $1$ is chosen as the chairperson. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the first line.
- Let’s consider the case where the assembly member $2$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the
council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the second line.
- Let’s consider the case where the assembly member $3$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $2$. Output $2$ in the third line.
该样例满足子任务 $1, 2, 4, 5, 6, 7$ 的限制。
**【样例解释 #2】**
该样例满足子任务 $1, 2, 5, 6, 7$ 的限制。
**【样例解释 #3】**
该样例满足子任务 $1, 2, 4, 5, 6, 7$ 的限制。
**【样例解释 #4】**
该样例满足所有子任务的限制。
**【数据范围】**
对于所有测试数据,$3 \le N \le 3 \times 10 ^ 5$,$1 \le M \le 20$,$0 \le A_{i, j} \le 1$,保证所有输入均为整数。
|子任务编号|分值|限制|
|:-:|:-:|:-:|
|$1$|$8$|$N \le 300$|
|$2$|$8$|$N \le 3000$|
|$3$|$6$|$M \le 2$|
|$4$|$19$|$M \le 10$|
|$5$|$15$|$M \le 14$|
|$6$|$22$|$M \le 17$|
|$7$|$22$|无|