$n$
$a_{1,1}{a}_{1,2}\dots a_{1,n}$
$a_{2,1}{a}_{2,2}\dots a_{2,n}$
$⋮$
$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{\}}_{i=1}^n$ 與 $\{c_i{\}}_{i=1}^n$ 為任意一個發射總次數最低的策略，其中

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

測資限制

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

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

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

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

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

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

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

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

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

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

2021 TOI 入營考 pE
testdata set by Omelet