IOI '99 - Antalya-Belek, Turkey

A Strip of Land

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 (x,y), where x is the horizontal (west-east) and y is the vertical (south-north) coordinate. The height of every square is shown on the map.

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

  1. the height difference between the highest and the lowest squares of the region is less than or equal to a given limit C, and
  2. 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.

Input

The first line contains three integers: the number of squares in the east-west direction, U (1 ≤ U ≤ 700), the number of squares in the north-south direction, V (1 ≤ V ≤ 700), and C (0 ≤ C ≤ 10).
Each of the following V lines contains the integers Hxy (-30 000 ≤ Hxy ≤ 30 000) for x = 1,…,U. More specifically, Hxy occurs as the xth number on the (V-y+2)th input line.

Output

The output should consist of a single line containing four space-separated integers describing the region found: Xmin, Ymin, Xmax, Ymax, where (Xmin , Ymin) are the coordinates of the southwest corner square, and (Xmax, Ymax) are the coordinates of the northeast corner square of the region.

Sample Input

10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 45 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41

Sample Output

4 5 8 11
Note: the bolded region in the input map corresponds to the region indicated in the output.

All Submissions
Best Solutions


Point Value: 25 (partial)
Time Limit: 5.00s
Memory Limit: 32M
Added: Aug 22, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

ryuuga on Jul 11, 2010 - 2:57:42 am UTC oops
  • (0/0)
Thank you.
that explains and fixes it.
example worked both ways(it starts 5 above and below bottom/top), and I rarely see those coordinate systems
Still too slow for last 7 cases, but works for others

ryuuga on Jul 09, 2010 - 7:23:42 am UTC
  • (0/0)
case 1 seems to be completely wrong for the judge... my program should work for that case, even though it is too slow
What does the judge check the answers against?

bbi5291 on Jul 11, 2010 - 2:23:04 am UTC Re: ...
  • (0/0)
The output file that the site shows you contains the largest possible area. If the region you output has this area and also satisfies the criteria, that case is judged as correct.

I think that the judge is correct, and that you forgot that y-coordinates increase from bottom to top.