RR và domino

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 640M
Input: stdin
Output: stdout
Author:
ngfam
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

RR là một tay chơi ở casino. Trên bàn casino có ~n~ hàng và ~m~ cột, trên mỗi ô có một con số, RR có ~k~ quân domino ~(1 \times 2)~ trên tay, RR phải đặt toàn bộ các quân domino xuống bàn sao cho chúng không đè lên nhau. Số tiền RR thu được sẽ bằng tổng của tích 2 số của những ô nằm trên vị trí của quân domino.

Input

Gồm nhiều bộ test mỗi test dòng đầu tiên là 3 số ~n, m, k (1 \leq n, m \leq 30, 1 \leq k \leq 200)~

~n~ dòng sau mỗi dòng ~m~ số là số được ghi tại một ô ~(1 \leq a_{ij} \leq 100)~

Output

Với mỗi test in số tiền lớn nhất mà RR có thể kiếm được

Example

2 2 2
1 4
3 2
3 3 1
9 1 1
1 4 4
1 4 4

11
16

Comments

Please read the guidelines before commenting.


  • 0
    KAKOII  commented on April 15, 2025, 6:00 a.m.

    Lời giải:

    Ta xem bàn casino như một bàn cờ với các ô đen trắng!

    Bàn cờ

    Tiếp theo, ta xây dựng một đồ thị hai phía với tập ~X~ gồm các ô đen và ~Y~ gồm các ô trắng.

    Ta xây dụng mạng kèm chi phí từ đồ thị hai phía trên như sau:

    1. Xây dựng các cung nối đỉnh nguồn ~S~ với các đỉnh ở tập ~X~. Các cung này có chi phí là ~0~, và sức chứa bằng ~1~.

    2. Xây dựng các cung nối các đỉnh ở tập ~Y~ với đỉnh thu ~T~. Các cung này có chi phí là ~0~, và sức chứa bằng ~1~.

    3. Xây dụng các cung nối đỉnh ~u~ thuộc ~X~ với các đỉnh ~v~ thuộc ~Y~ sao cho ~uv~ là hai điểm kề nhau trên bàn casino. Các cung này có chi phí tích giá trị hai ô, và sức chứa bằng ~1~.

    Sau khi đã xây dựng xong mạng, ta sửa code mẫu trong bài viết Luồng với chi phí cực tiểu trên VNOI wiki sao cho nó sẽ tìm luồng cực đại với chi phí cực đại trên mạng.

    Bình luận: Có thể mình sai nhưng test của bài này có lẽ không đúng, vì bài yêu cầu đặt đúng ~k~ domino trên bàn, mà code của mình lại bị sai vì làm đúng theo yêu cầu!


  • 1
    KAKOII  commented on March 25, 2025, 12:50 a.m.

    Bài này hình như có bộ test không bỏ đủ được k quân domino hay sao ấy ạ


  • 8
    madv809  commented on April 28, 2021, 2:18 p.m.

    Ad sửa lại thành "... phải đặt HẾT các quân domino..." được không ạ, em cứ tưởng đặt bao nhiêu tùy thích miễn sao <= k là được nên ăn WA 2 phát liên tiếp:v


    • 5
      leduykhongngu  commented on April 29, 2021, 3:32 a.m.

      Mình sửa rồi nhé :3 cám ơn bạn