Ma Trận Ràng Buộc Lưu Lượng
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Xây dựng một ma trận số nguyên không âm kích thước R × C sao cho:
- Tổng các phần tử trên hàng i nằm trong đoạn [rowL_i, rowR_i].
- Tổng các phần tử trên cột j nằm trong đoạn [colL_j, colR_j].
- Mỗi ô (i, j) có giá trị nằm trong đoạn [L_{i,j}, R_{i,j}].
Hãy tìm tổng các phần tử của ma trận lớn nhất có thể, hoặc in -1 nếu không tồn tại ma trận thỏa mãn.
Dữ liệu vào
- Dòng đầu: hai số nguyên R và C (1 ≤ R, C ≤ 60).
- R dòng tiếp theo: hai số nguyên rowL_i, rowR_i.
- C dòng tiếp theo: hai số nguyên colL_j, colR_j.
- R × C dòng tiếp theo (theo thứ tự hàng rồi cột): hai số nguyên L_{i,j}, R_{i,j}.
Dữ liệu ra
- Tổng lớn nhất có thể của ma trận, hoặc -1 nếu vô nghiệm.
Ví dụ
| Input | Output |
|---|---|
| 2 2\n3 5\n4 6\n3 5\n3 5\n1 3\n1 3\n1 3\n1 3 | 10 |
Giới hạn
- 1 ≤ R, C ≤ 60
- 0 ≤ L ≤ R ≤ 10^9
Community Discussion