Problem2365--暑假提高组模拟测试卷三 T4乌鸦喝水

2365: 暑假提高组模拟测试卷三 T4乌鸦喝水

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:][下载测试数据]

Description

在一片广袤的森林里,有一只名叫乌鸦的黑鸟,乌鸦是出了名的聪明。然而,它却有个奇特的习惯,收集各色各样的石头。每当找到一颗特别或是形状奇特的石头,乌鸦就会兴高采烈地将其收入自己的巢中。

有一天,乌鸦在森林的另一角落发现了一个浅浅小水塘。塘底躺着许多五彩斑斓的石头,每一种都闪耀着诱人的光芒。乌鸦见状,灵光一动。它叼起一颗石头,飞到了水塘边。乌鸦用石头去击溅起水花,然后迅速张开嘴巴,欣赏四溅的水珠,乌鸦希望看到的水花尽量大,但是乌鸦不希望石子溅起水花后有石子露出水面,这意味着乌鸦使用的石头体积要尽量大,且不能超过水面。

由于乌鸦很聪明但又没有那么聪明,为了简化问题,我们把石子认为是长方体,池塘表面认为是矩形,矩形大小为 m * n,对池塘建立直角坐标系,池塘四周都是竖直的,并测得了每个单位方格的深度(深度表示池塘表面到池塘底部的距离)。当石子沉入水中时,石子会一直下沉直到碰到池底。沉底时,石子的顶面会和池塘的表面平行,石子的边缘会和网格对齐。石子排开了一部分水,这会使池塘的水位上升(排开水的体积等于石头的体积)。池塘四周的墙面足够高,所以水不会溅出来。

例如,在下图中,左边的图表示池塘的形态,中间的图表示一种体积为 3 的放置方法,右边的图表示一种体积为 4 的放置方法。这也是能够藏下的最大体积。注意,如果右边的图的石子再变高 1 单位,它的顶面就能被看到了,因为此时它的顶面和水面一样高,注意,石子与水面一样高也是不可行的。



乌鸦只想丢一次石头,它想知道在不看到石子情况下,能够丢下池塘的石子最大体积是多少?你能告诉它吗?


Input

第一行输入包含四个整数 a,b,m,n,其中 a 和 b 表示石子表面一边尺寸不能超过 a,另一边尺寸不能超过 b,m 和 n 表示池塘表面的大小为 m* n。

接下来有 m 行数据,每行有 n 个整数,其中第 i+1 行第 j 列的整数为 d_{i,j},表示池塘 (i,j) 这个单元格的深度。



Output

第一行包含一个整数,表示能**完全淹没**在池塘里的满足要求的石子的最大体积。如果不存在能淹没在池塘里的石子,输出 0。

注意:完全淹没的意思是,石子表面需要**严格低于**池塘水面。

Sample Input

## 样例 #1

### 样例输入 #1

```
3 1 2 3
2 1 1
2 2 1
```

### 样例输出 #1

```
4
```

## 样例 #2

### 样例输入 #2

```
4 1 1 5
2 0 2 2 2
```

### 样例输出 #2

```
12
```

## 样例 #3

### 样例输入 #3

```
2 3 3 5
2 2 2 2 2
2 2 2 2 2
2 2 2 2 2
```

### 样例输出 #3

```
18
```

HINT

【样例 1 解释】

样例 1 如题目描述中的示意图图,体积最大的方案是丢入一个 2* 1 * 2 的石子(黄色部分),会使得水面上升 \frac{2 * 1 * 2}{2 * 3}=\frac{2}{3}\approx 0.66,此时水面为 2.66,是一种合法的方案。

但是,如果石子在上升一个高度,变成 2* 1 * 3,那么水面上升为 \frac{2 * 1 * 3}{2 * 3}=1,水面高度变为 3 和石子高度一样,是一种不合法的方案。

可以证明,该方案的石子体积是最大的。

【数据范围】

有 6% 的数据满足 m =2,n = 2;

另有 12% 的数据满足 m,n < 4;

另有 37% 的数据满足 m,n < 65;

另有 10% 的数据满足池塘所有单元格的深度相等;

另有 9% 的数据满足只有一个格子的深度与其他格子不同;

对于 100% 的数据满足 1 < a,b,m,n < 500,0 < d_{ij} < 10^9。



Source/Category

 

[Submit] [Status]