CSES2131 网格拼图 II
#CS2131. 网格拼图 II
网格拼图 II
题目背景
翻译自 CSES-2131 题。
题目描述
有一个 n×nn \times nn×n 的网格，每个格子里有一定数量的金币。
你知道每一行和每一列需要选择多少个格子来获取金币。你可以从每个你选择的格子中获取所有金币。那么，如何选择这些格子才能使得你获得最大的金币数量，并且满足给定的条件？
输入格式
第一行包含一个整数 n：网格的大小。行和列的编号为 1,2,...,n1, 2, ..., n1,2,...,n。
第二行包含 n 个整数 a1,a2,...,ana_1, a_2, ..., a_na1,a2,...,an：表示你必须从第 i 行选择 aia_iai 个格子。
第三行包含 n 个整数 b1,b2,...,bnb_1, b_2, ..., b_nb1,b2,...,bn：表示你必须从第 j 列选择 bjb_jbj 个格子。
接下来有 n 行，每行包含 n 个整数 cijc_{ij}cij：表示第 i 行第 j 列格子里的金币数量。
你可以假设 a1+a2+...+ana_1 + a_2 + ... + a_na1+a2+...+an 和 b1+b2+...+bnb_1 + b_2 + ... + b_nb1+b2+...+bn 相等。
输出格式
首先输出一个整数 k：表示你可以收集到的最大金币数量。
然后输出 n 行，每行描述你选择的格子。如果选择某个格子，则用 X 表示，否则用 . 表示。
如果无法满足条件，输出 -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
32
.....
..X..
.XX.X
XX...
.....
说明/提示
0≤ai≤n0 \leq a_i \leq n0≤ai≤n；
0≤bj≤n0 \leq b_j \leq n0≤bj≤n；