← 返回题目列表

AtCoder · gigacode_2019_d

D. 建造房屋

中文机器翻译题面 查看原题

配点: 100 点

問題文

Giga君买了电脑,学了编程,进了公司,赚了钱,终于盖了房子!
他居住的泰拉市是 H 行 W 它由列网格表示。从上面 i 行,从左至第 j 该列中的单元格是 它由 (i, j) 表示。还有,质量 (i, j) 的土地价格为 A_{i, j} 这是日元。

现在,可以按如下方式建造房屋。

  • 您可以选择并购买泰拉城中的多个方块(土地)。鳟鱼 (i, j) 买 A_{i, j} 花费日元。要购买的正方形面积必须用一个长方形表示。
  • 购买土地 在全体建造一座房子。 如果您购买S 方块,您可以使用以下方法建造房屋 S×K 花费日元。

例如,K = 5 ,如图1所示构建时, (1+4)+(2 \times 5)=15 Yen,当构建类似(图2)的东西时, (6+3+4+1)+(4 \times 5)=34 花费日元。然而,图中的数字是每个方格的土地价格。

另外,无法购买下面(图3)或(图4)中灰色所示的土地。不可能.这是因为购买的土地面积 1 这是因为它不是由两个矩形表示的。

他目前 V 我有日元,可以用我所有的资产购买豪宅。他想买一套空间尽可能大的房子。
找出他当前可以购买的房子的最大可能面积。另外,如果买不起房子 请输出 0 。但房子的面积和购买的长方形面积是一样的。

制約

  • 1 \leq H, W \leq 125
  • 1 \leq A_{i, j}, K \leq 1 \ 000 \ 000 \ 000
  • 1 \leq V \leq 1 \ 000 \ 000 \ 000 \ 000 \ 000 (=10^{15})
  • 输入全为整数。

部分点

该问题分为多个子任务,如果您正确回答了该子任务中的所有测试用例,则视为您已正确回答了“该子任务”。
提交的源代码的分数是您正确回答的子作业分数的总和。

  1. (11 点) H = 1, W = 1
  2. (17 点) H = 1, W \leq 20
  3. (28 点) H \leq 20, W \leq 20
  4. (27 点) H \leq 75, W \leq 75
  5. (17 分) 没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

H W K V
A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, W}
A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, W}
A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, W}
 :
A_{H, 1} A_{H, 2} A_{H, 3} ... A_{H, W}

出力

找到他可以购买的房子的最大可能面积。
但是,如果你买不起房子, 请输出 0 。


入力例 1

1 1 200 500
300

出力例 1

1

他买了唯一的广场并盖了房子。200 + 300 = 500 需要日元,而且还勉强够用。
这个输入示例是 它满足 1 约束。


入力例 2

1 8 10 200
30 40 10 20 30 40 10 20

出力例 2

6

例如,假设他购买土地如下。

在这种情况下,购买土地 10 + 20 + 30 + 40 + 10 + 20 = 130 日元,盖房子 6 × 10 = 60 由于需要日元,所以总成本是 130 + 60 = 190 我需要日元,200 由于它小于圆,因此面积 6 房子可以建造。
此外,该区域 7 没有办法买比这个更高的房子了。
这个输入示例是 它满足 2 约束。


入力例 3

5 5 10 17
12 19 25 13 25
14 16 18 11 10
19 17 24 26 12
23 11 16 19 14
18 23 27 11 16

出力例 3

0

对于此输入示例,您无法购买房屋。因此,0 。


入力例 4

4 7 10 240
17 12 15 18 19 15 23
22 12 41 16 27 10 10
15 69 18 11 10 23 15
12 20 13 12 17 18 15

出力例 4

9

例如,如果您购买土地并 当您在 9 买房时,235 需要日元,但我们勉强够用。