BLAND - Exchanging Land for a Fan

no tags 

The landlord has a rectangular land divided into a grid of M rows and N columns. The rows are numbered from the top to the bottom starting from 1, and the columns are numbered from the left to the right starting from 1. The intersection between the ith row and the jth column (i=1..M,j=1..N) has a height of hij. The landlord has offered to exchange his land for Bom's magic fan. Here's the condition of the offer:

  • Bom can pick two sub-pieces of land (one for housing and one for gardening). Both pieces should have rectangular shape and contain a whole number of cells.
  • Each piece should have its height difference not exceeding K, i.e. the difference between its highest cell and its lowest cell does not exceed k.
  • The two pieces should not overlap each other (though they can be in contact).
  • Please help Bom to pick the two pieces of land satisfying the above conditions and have the largest sum of areas.


  • The first line contains three integers M, N and K (M,N≤300).
  • Each line in the next M lines contains N integers hij describing the land.(K,|hij|<109)


A single number that is the largest possible sum of areas of Bom's two pieces of land.


3 4 0
1 2 3 1
1 9 9 1
2 2 2 2


Note: There are 50% test cases in which m,n≤50.

Added by:Duc
Time limit:0.200s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:VNOI Marathon 2009
Round 3
Problem Setter: Đỗ Đức Đông