CSES - Grid Puzzle II | Câu đố trên lưới II
Xem PDF
Điểm:
2100 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một ma trận \(n × n\) với mỗi ô chứa một số tiền ở trong.
Bạn chỉ được chọn một số ô nhất định trên mỗi dòng hoặc cột. Bạn nhận được tất cả tiền từ mỗi ô vuông bạn chọn. Số tiền tối đa bạn có thể thu thập được là bao nhiêu và làm thế nào bạn có thể chọn các ô sao cho thỏa mãn các điều kiện đã cho?
Input
- Dòng đầu tiên chứa số nguyên \(n\): kích thước của lưới. Các hàng và cột được đánh số \(1,2,…, n\).
- Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2,…, a_n\): Bạn phải chọn chính xác \(a_i\) ô từ hàng thứ \(i\).
- Dòng tiếp theo chứa \(n\) số nguyên \(b_1, b_2,…, b_n\): Bạn phải chọn chính xác \(b_j\) ô từ cột thứ \(j\).
- Cuối cùng, có \(n\) dòng mô tả ma trận. Tổng của \(a_1, a_2,…, a_n\) và \(b_1, b_2,…, b_n\) bằng nhau.
Output
- Dòng đầu in ra một số nguyên \(k\): số tiền tối đa bạn có thể nhận được. Sau đó, in \(n\) dòng mô tả bạn chọn ô nào (\(X\) nghĩa là bạn chọn ô đấy, \(.\) nghĩa là bạn không chọn).
- Nếu không có cách chọn, in một số \(-1\).
Constraints
- \(1\leq n \leq 50\)
- \(1\leq a_i \leq n\)
- \(1\leq b_j \leq n\)
- \(1\leq c_{ij} \leq 1000\)
Example
Sample input
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
Sample output
32
.....
..X..
.XX.X
XX...
.....
Bình luận
CSES - Grid Puzzle II | Câu đố trên lưới II
Cho một lưới \(n \times n\), mỗi ô của lưới có chứa một số đồng xu.
Bạn biết trước rằng mình chỉ có thể chọn một số ô nhất định từ mỗi hàng hoặc cột của lưới. Bạn sẽ nhận được toàn bộ số tiền trong các ô mà bạn chọn. Số tiền tối đa mà bạn có thể thu thập được là bao nhiêu, và bạn sẽ chọn các ô như thế nào để thoả mãn các điều kiện đã cho?
Input
Output
Xnếu bạn chọn một ô hoặc.nếu bạn không chọn ô đó).-1duy nhất.Example
Test 1
Input
Output