OI题库

【题目描述】

Dingilville的居民正设法找到一块地来修建机场。他们已经有了这片地区的地图。地图是一个由单位格组成的矩形网格，每个单位格由一个整数对(x,y)确定，其中x是横坐标（东到西），y是纵坐标（南到北）。地图中标注了每格的海拔。

你的任务是找到一个由单位格组成的，面积最大（即包含最多单位格）的矩形地块，使得：

·地块中海拔最高和最低的单位格的海拔之差不超过给定的限制C。

·地块的宽度（即从西到东的距离）不超过100.

你需要输出满足条件地块的最大面积。

【输入格式】

输入文件的第一行有三个整数U,V,C，代表地图的大小和给定限制。

接下来的V行，每行有U个整数Hxy，给出了每格的海拔。

【输出格式】

输出一行一个正整数，即最大面积。

【样例输入】

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

【样例输出】

35

【提示】

样例如图：

1<=U<=700,1<=V<=700

0<=C<=10

-30000<=Hxy<=30000

西南角是（1,1），东北角是（U,V）

【来源】

IOI 1999 A Strip of Land