Cân bằng ma trận ngân sách
Points
100
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một ma trận số nguyên không âm $A$ kích thước $R \times C$. Bạn cần xây dựng một ma trận số nguyên không âm $B$ cùng kích thước $R \times C$ sao cho:
- Tổng các phần tử trên hàng $i$ của $B$ đúng bằng $R_i$ (với mọi $1 \le i \le R$).
- Tổng các phần tử trên cột $j$ của $B$ đúng bằng $C_j$ (với mọi $1 \le j \le C$).
- Tổng sai lệch $\sum_{i=1}^R \sum_{j=1}^C |B_{i,j} - A_{i,j}|$ là nhỏ nhất.
Nếu không tồn tại ma trận $B$ thỏa mãn, in ra -1.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $R, C$ ($1 \le R, C \le 20$).
- $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên $A_{i,j}$ ($0 \le A_{i,j} \le 1000$).
- Dòng tiếp theo chứa $R$ số nguyên $R_1, \dots, R_R$ ($0 \le R_i \le 10^5$).
- Dòng cuối cùng chứa $C$ số nguyên $C_1, \dots, C_C$ ($0 \le C_j \le 10^5$).
Dữ liệu ra
- In ra tổng sai lệch nhỏ nhất, hoặc
-1nếu không tồn tại.
Ví dụ
| Input | Output |
|---|---|
| 2 2 1 3 4 2 5 5 4 6 |
2 |
Giới hạn
- $1 \le R, C \le 20$.
- Thời gian chạy: 3 giây.
Community Discussion