CSES - Grid Puzzle II | Câu đố trên lưới II

View as PDF
All submissions
Best submissions
Author:
nhphucqt
Problem types
Points: 2100 (p) Time limit: 1.0s Memory limit: 512M Input: stdin Output: stdout

There is an \(n×n\) grid whose each square has some number of coins in it.

You know for each row and column how many squares you must choose from that row or column. You get all coins from every square you choose. What is the maximum number of coins you can collect and how could you choose the squares so that the given conditions are satisfied?

Input

  • The first input line has an integer \(n\): the size of the grid. The rows and columns are numbered \(1,2,…,n\).
  • The next line has n integers \(a_1,a_2,…,a_n\): You must choose exactly ai squares from the \(i\)th row.
  • The next line has n integers \(b_1,b_2,…,b_n\): You must choose exactly bj squares from the \(j\)th column.
  • Finally, there are n lines describing the grid. You can assume The sums of \(a_1,a_2,…,a_n\) and \(b_1,b_2,…,b_n\) are equal.

Output

  • First print an integer \(k\): the maximum number of coins you can collect. After this print n lines describing which squares you choose (\(X\) means that you choose a square, \(.\) means that you don't choose it).
  • If it is not possible to satisfy the conditions print only \(−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...  
.....

Comments

  • vanphukhang_0604 • 8:46 p.m. 14 aug, 2023 • ← edit 5

    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

    • Dòng đầu tiên chứa số nguyên \(n \ (1 \leq n \leq 50)\): kích thước của lưới. Các hàng và cột được đánh số \(1, 2, \ldots, n\).
    • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n \ (1 \leq a_i \leq 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, \ldots, b_n \ (1 \leq b_i \leq n)\): bạn phải chọn chính xác \(b_j\) ô từ cột thứ \(j\). Tổng các giá trị \(a_1, a_2, \ldots, a_n\) bằng tổng các giá trị \(b_1, b_2, \ldots, b_n\).
    • \(n\) dòng cuối cùng mô tả lưới. Ô \((i, j)\) chứa \(c_{ij}\) đồng xu \((0 \leq c_{ij} \leq 1000)\).

    Output

    • Dòng đầu in ra một số nguyên \(k\): số tiền tối đa mà bạn có thể thu thập được.
    • Sau đó, in ra \(n\) dòng mô tả cách bạn chọn các ô trên lưới (in X nếu bạn chọn một ô hoặc . nếu bạn không chọn ô đó).
    • Nếu không có cách chọn nào thoả mãn, hãy in ra một số -1 duy nhất.

    Example

    Test 1

    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
    Output 
    32  
.....
..X..
.XX.X
XX...
.....
    0
    Reply