$n$
$a_{1,1}\ a_{1,2}\ \dots\ a_{1,n}$
$a_{2,1}\ a_{2,2}\ \dots\ a_{2,n}$
$\vdots$
$a_{n,1}\ a_{n,2}\ \dots\ a_{n,n}$

• $n$ 代表玩家數，亦即棋盤的列數與行數。
• $a_{i,j}$ 代表 $(i,j)$ 空域的小行星質量。

$m$
$r_1\ r_2\ \dots\ r_n$
$c_1\ c_2\ \dots\ c_n$

• $m$ 為一整數代表清除所有小行星的最低發射次數

• $\{r_i\}^ n_{i=1}$ 與 $\{c_i\}^ n_{i=1}$ 為任意一個發射總次數最低的策略，其中

  • $r_i$ 為一非負整數，代表朝著第 $i$ 列發射的次數。
  • $c_i$ 為一非負整數，代表朝著第 $i$ 行發射的次數。
  • 輸出的 $r_i, c_i$ 必須為 $0$ 到 $2\times 10^ 6$ 之間的非負整數
  • 若輸出的 $m$ 為正確的最小次數但發射方案錯誤仍可得到部分分數，得分算法請參照下方評分說明一節。

測資限制

• $1\leq n\leq 500$。
• $0\leq a_{i,j}\leq 2\times 10^ 6$。（$i,j\in\{1,2,\dots,n\}$）
• 輸入的數均為整數。

評分說明
本題共有四組子任務，條件限制如下所示。

1. (20%) $n\leq 20$，且 $a_{i,j}\in\{0,1\}$。
2. (40%) $n\leq 70$，且 $a_{i,j}\in\{0,1\}$。
3. (35%) $n\leq 70$。
4. (5%) 無額外限制。

每一子任務可有一或多筆測試資料。在一子任務中，若所有測試資料的輸出均滿足以下條件，即可獲得滿分：

• 最小總發射次數 $m$ 正確。
• 發射策略 $\{r_i\}^ n_{i=1}$ 與 $\{c_i\}^ n_{i=1}$ 滿足題目要求。

若子任務中有任一筆測試資料的輸出滿足以下任一條件，將收到 Wrong Answer 且無法在此子任務中獲得任何分數：

• 只輸出一行 $m$ 但沒有輸出 $r_i, c_i$。
• 其它輸出格式錯誤，例如 $r_i, c_i$ 不是介於 $0$ 到 $2 \times 10^ 6$ 之間的情形。
• 最小總發射次數 $m$ 錯誤。

若子任務中所有測試資料的輸出，格式與最小總發射次數 $m$ 皆正確，但發射策略不符合題目要求 （$\{r_i\}^ n_{i=1}$ 與 $\{c_i\}^ n_{i=1}$ 總和與 $m$ 不相等也可以），可在此子任務中獲得 40% 的分數。也就是說如果只會計算總和但不會計算解的方案時在 $m$ 後面輸出兩行 $n$ 個 $0$：

$m$
$0\ 0\ \dots\ 0$
$0\ 0\ \dots\ 0$

可以得到該子任務 40% 的分數。

2021 TOI 入營考 pE
testdata set by Omelet