BLAND - Exchanging Land for a Fan

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.

Link đọc đề trên VNOJ

Giá trị chiếc quạt mo

Phú ông có một mảnh đất hình chữ nhật được chia thành lưới ô vuông gồm M hàng và N cột. Các hàng của lưới được đánh số từ trên xuống dưới bắt đầu từ 1, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1. Ô nằm giao của hàng i và cột j là ô đất i,j (i=1..M,j=1..N) có độ cao là h ij . Phú ông đã đưa ra đề nghị đổi chiếc quạt mo lấy đất như sau:

  • Bờm được quyền chọn 2 mảnh đất con (một mảnh để làm nhà, một mảnh để trồng rau), hai mảnh đều có dạng hình chữ nhật và chứa nguyên các ô.
  • Mỗi mảnh đất có độ chênh lệch không quá K, nghĩa là hiệu độ cao của ô có độ cao nhất với ô có độ cao thấp nhất không vượt quá K.
  • Hai mảnh đất được chọn không không giao nhau nhưng có thể tiếp xúc nhau.
  • Hãy giúp Bờm chọn được hai mảnh đất thỏa mãn điều kiện của phú ông và có tổng diện tích là lớn nhất.

Dữ liệu

  • Dòng đầu là 3 số M,N và K (M,N≤300)
  • M dòng sau, mỗi dòng gồm N số nguyên h ij mô tả mảnh đất (K,|h ij |<10 9 )

Kết quả

Chứa một số là tổng diện tích lớn nhất tìm được.

Ví dụ 

Dữ liệu
3 4 0
1 2 3 1
1 9 9 1
2 2 2 2	

Kết quả
6

Lưu ý: Có 50% số test với m,n≤50.

  • Người up: paulmcvn
  • Nguồn bài: VNOI Marathon 2009Round 3Problem Setter: Ðỗ Ðức Ðông