Ma Trận Ràng Buộc Lưu Lượng

Buổi 47 — Luồng cực đại (Dinic)
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề 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
Draft saved