AT_arc177_e [ARC177E] Wrong Scoreboard

AtCoder World Tour Finals 2800 有 $N$ 名选手参加，比赛共设置了 $5$ 道题目。每道题目的分值都是不小于 $1$ 的整数，并且题目的编号 $1$ 到 $5$ 满足分值**广义单调递增**（即后面的题目分值不小于前面的题目）。这里不设部分分。 此外，排名规则与通常的 AtCoder 规则相同，具体如下（本题中不会出现总分和罚时都相同的情况）： - 排名规则：总分高的选手排名更高；如果总分相同，则罚时更少的选手排名更高。 现在，负责 AtCoder World Tour Finals 采访的青木记者记录下了以下信息： 1. 参赛人数 $N$。 2. 每位选手解答每道题目的情况。若 $A_{i,j}=1$，表示第 $i$ 位选手（$1\leq i\leq N$）解出了第 $j$ 题，否则 $A_{i,j}=0$。 3. 每位选手的排名。第 $i$ 位选手（$1\leq i\leq N$）获得了 $R_i$ 名。 但在准备写稿时，他发现自己没有记录分值和罚时的信息，并且也意识到自己记录的信息可能存在矛盾。请你解决以下问题： > 假设记录 1 和记录 2 是正确的。记第 $i$ 位选手的实际排名为 $D_i$，请你求出二乘误差之和 $(D_1-R_1)^2 + (D_2-R_2)^2 + \dots + (D_N-R_N)^2$ 的最小可能值。 给定 $T$ 个测试用例，请分别输出每个测试用例的答案。

输入按以下格式从标准输入读入。这里 $\mathrm{case}_i$ 表示第 $i$ 个（$1\leq i\leq T$）测试用例。 > $T$ > $\mathrm{case}_1$ > $\mathrm{case}_2$ > $\vdots$ > $\mathrm{case}_T$ 每个测试用例的输入格式如下： > $N$ > $A_{1,1}$ $A_{1,2}$ $A_{1,3}$ $A_{1,4}$ $A_{1,5}$ > $A_{2,1}$ $A_{2,2}$ $A_{2,3}$ $A_{2,4}$ $A_{2,5}$ > $\vdots$ > $A_{N,1}$ $A_{N,2}$ $A_{N,3}$ $A_{N,4}$ $A_{N,5}$ > $R_1$ $R_2$ $\cdots$ $R_N$

请输出答案。

### 限制条件 - $1\leq T\leq 10^5$ - $2\leq N\leq 3\times 10^5$ - $A_{i,1},A_{i,2},A_{i,3},A_{i,4},A_{i,5}$ 为 $0$ 或 $1$（$1\leq i\leq N$） - $A_{i,1}+A_{i,2}+A_{i,3}+A_{i,4}+A_{i,5}\geq 1$（$1\leq i\leq N$） - $1\leq R_i\leq N$（$1\leq i\leq N$） - $R_1,R_2,\dots,R_N$ 互不相同 - 所有测试用例中 $N$ 的总和不超过 $3\times 10^5$ - 所有输入均为整数 ### 样例解释 1 本输入共包含 $6$ 个测试用例，先说明第 $1$ 个测试用例。 > 假设如下情况： > > - 第 $1,2,3,4,5$ 题的分值分别为 $100$、$500$、$800$、$900$、$1300$。 > - 第 $1,2,3,4$ 位参赛者的罚时分别为 $90$ 分、$80$ 分、$70$ 分、$60$ 分。 > > 此时，排名表如下，二乘误差之和为 $(2-1)^2 + (3-2)^2 + (1-3)^2 + (4-4)^2 = 6$。不存在使二乘误差之和小于 $5$ 的方法，因此答案为 $6$。 > > | 参赛者 | 问 1 | 问 2 | 问 3 | 问 4 | 问 5 | 总分 | 罚时 | 排名 | > |:------:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:| > | **1** | - | 500 | 800 | - | - | 1300 | 90 | 2 | > | **2** | 100 | - | - | 900 | - | 1000 | 80 | 3 | > | **3** | 100 | 500 | - | 900 | - | 1500 | 70 | 1 | > | **4** | 100 | - | 800 | - | - | 900 | 60 | 4 | 接下来说明第 $2$ 个测试用例。 > 假设如下情况： > > - 第 $1,2,3,4,5$ 题的分值分别为 $1000$、$1400$、$2000$、$2000$、$2718$。 > - 第 $1,2,\dots,8$ 位参赛者的罚时分别为 $295$ 分、$286$ 分、$242$ 分、$236$ 分、$277$ 分、$288$ 分、$187$ 分、$299$ 分。 > > 此时，排名表如下。对于任意 $i$（$1\leq i\leq N$），第 $i$ 位参赛者的排名均为 $R_i$，因此二乘误差之和为 $0$。 > > | 参赛者 | 问 1 | 问 2 | 问 3 | 问 4 | 问 5 | 总分 | 罚时 | 排名 | > |:------:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:| > | **1** | - | 1400 | - | - | - | 1400 | 295 | 7 | > | **2** | 1000 | 1400 | - | 2000 | - | 4400 | 286 | 4 | > | **3** | - | 1400 | 2000 | - | 2718 | 6118 | 242 | 2 | > | **4** | 1000 | - | - | - | - | 1000 | 236 | 8 | > | **5** | 1000 | 1400 | - | 2000 | - | 4400 | 277 | 3 | > | **6** | - | 1400 | - | - | - | 1400 | 288 | 6 | > | **7** | - | - | - | 2000 | - | 2000 | 187 | 5 | > | **8** | - | 1400 | 2000 | 2000 | 2718 | 8118 | 299 | 1 | 由 ChatGPT 4.1 翻译