CSES 2131 - Grid Puzzle II

有一個 \(n \times n\) 的方格圖，每一格裡都有若干枚硬幣。

你知道每一列與每一行各必須選出多少格。你會得到所選每一格中的所有硬幣。請問你最多能收集到多少硬幣，以及要如何選格子才能滿足給定的條件？

輸入格式

第一行有一個整數 \(n\)：方格圖的大小。列與行的編號皆為 \(1, 2, \dots, n\)。

下一行有 \(n\) 個整數 \(a_1, a_2, \ldots, a_n\)：你必須從第 \(i\) 列恰好選出 \(a_i\) 格。

下一行有 \(n\) 個整數 \(b_1, b_2, \ldots, b_n\)：你必須從第 \(j\) 行恰好選出 \(b_j\) 格。

最後有 \(n\) 行描述這個方格圖。你可以假設 \(a_1, a_2, \ldots, a_n\) 的總和與 \(b_1, b_2, \ldots, b_n\) 的總和相等。

輸出格式

先輸出一個整數 \(k\)：你能收集到的最多硬幣數。接著輸出 \(n\) 行描述你選了哪些格子（X 表示選這一格，. 表示不選）。

如果無法滿足條件，則只輸出 \(-1\)。

範例輸入 1

5
0 1 3 2 0
1 2 2 0 1
2 5 1 5 1
0 2 5 1 2
3 8 9 3 5
1 4 3 7 3
0 3 6 2 8

範例輸出 1

32
.....
..X..
.XX.X
XX...
.....

限制

• \(1 \le n \le 50\)
• \(0 \le a_i \le n\)
• \(0 \le b_j \le n\)
• \(0 \le c_{ij} \le 1000\)

題目來源

CSES - Grid Puzzle II

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。