BGMAGIC - MAGIC
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274766/problem/S
Đại Ca Đi Học rất thích chơi với các bảng số. Lần này, Đại Ca có một bảng kích thước n×m. Mỗi ô của bảng có 1 số nguyên dương. Bảng là đẹp nếu các số trong mỗi cột sắp xếp theo thứ tự tăng nghiêm ngặt từ trên xuống dưới, và các số trong mỗi hàng phải xếp theo thứ tự tăng nghiêm ngặt từ trái qua phải. Ví dụ
1 2 3 4
3 4 5 6
5 6 7 8
7 8 9 10
Bảng Siêu đẹp là bảng đẹp , nhưng các số ở 2 ô chéo nhau bất kỳ (2 ô có chung nhau đúng 1 đỉnh) phải khác tính chẵn lẻ. Bảng sau là bảng đẹp, nhưng không phải bảng siêu đẹp
1 2
4 6
Chú ý bảng 4x4 bên trên là bảng Siêu Đẹp.
Cho một bảng số khuyết 1 số ô, hãy giúp Đại Ca Đi Học điền các số vào tất cả các ô khuyết, để bảng trở thành bảng Siêu Đẹp và tổng tất các số trong bảng là nhỏ nhất có thể.
Input
- Dòng đầu ghi 2 số n và m (1 ≤ n, m ≤ 2000) là kích thước bảng.
- Sau đó là n dòng, mỗi dòng ghi m số nguyên c (0 ≤ c ≤ 2000). Ô có số 0 là ô trống cần điền số vào. Số được điền có thể giống nhau, không bị giới hạn ≤ 2000.
Output
- In ra tổng các ô bé nhất sau khi điền vào các ô trống để tạo ra bảng siêu đẹp. In ra -1 nếu không thể điền để tạo thành bảng siêu đẹp
Example
Input: 4 4 1 2 3 0 0 0 5 6 0 4 7 8 7 0 0 10 Output: -1
Input: 4 4 1 2 3 0 0 0 5 6 0 0 7 8 7 0 0 10 Output: 88
- Người up: voj
- Nguồn bài: Bắc Giang PreVOI 2015