BLAND - Exchanging Land for a Fan

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à hij. 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 hij mô tả mảnh đất (K,|hij|<109)

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.


Được gửi lên bởi:Jimmy
Ngày:2009-07-21
Thời gian chạy:0.200s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:VNOI Marathon 2009
Round 3
Problem Setter: Đỗ Đức Đông

hide comments
2020-06-27 13:54:32
Tham khảo:
Code: http://megaurl.in/yH4X53j
2018-03-14 11:37:46
2 buổi chiều vẫn k ăn thua. nhọc...
2017-11-24 02:17:00
nhật hào sạch

2017-11-18 02:02:03
bfs đc ko nhỉ ???
2017-09-04 10:20:13
from Dinh Truong Lam

trau cung ac ^^
2016-09-27 03:17:13
Code:
http://shink.in/lgQGv
2016-06-20 04:24:55
lần nào làm deque cũng sub đến tê liệt

Last edit: 2016-06-21 12:10:38
2016-01-31 16:04:30 Nguyễn Thành Nhân
ez
2015-10-27 19:47:31
Blog Thuật toán SPOJ hy vọng giúp được cho mọi người : http://www.oni.vn/uR57W
2013-06-09 19:06:12 Cottontail Tee
time chặt quá X_X
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.