## A STRIP OF LAND- Return to The IOI'99 Competition
PROBLEM
The residents of Dingilville are trying to locate a region
to build an airport. The map of the land is at hand. The map is a rectangular grid of unit
squares, each identified by a pair of coordinates ( Your task is to find a rectangular region of squares with the largest area (i.e. a rectangular region consisting of the largest number of squares) such that - the height difference between the highest and the lowest squares of the region is less
than or equal to a given limit
*C*, and - the width (i.e. the number of squares along the west-east direction) of the region is at most 100.
In case there is more than one such region you are required to report only one of them.
- 1 <=
*U*<=700, 1 <=*V*<=700 where*U*and*V*designate the dimensions of the map. More specifically,*U*is the number of squares in the west-east direction, and*V*, in the south-north direction. - 0 <=
*C <=*10 - -30,000 <=
*H*<= 30,000 where the integer_{xy}*H*is the height of the square at coordinates (_{xy}*x*,*y*), 1 <=*x*<=*U*, 1 <=*y <= V.* - The southwest corner square of the map has the coordinates (1,1) and the northeast
corner has the coordinates (
*U*,*V*).
INPUT
The input is a text file named - The first line contains three integers:
*U*,*V*and*C*. - Each of the following
*V*lines contains the integers*H*for_{xy}*x =*1,…,*U*. More specifically,*H*occurs as the_{xy}*x*’th number on the (*V*-*y+2)*’th input line.
OUTPUT
The output must be a text file named four integers locating the region found: Y,
_{min}X, _{max}Y, where (_{max}X , _{min}Y
) is the coordinates of the southwest corner square, and (_{min}X, _{max}Y
) is the coordinates of the northeast corner square of the region. _{max}EXAMPLE
EVALUATION
Your program will be allowed to run 130 seconds. |