← 返回题目列表

AtCoder · jag2016secretspring_f

F. 土地继承

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

问题陈述

一个$N$的兄弟正在讨论继承父母遗产的事。 在父母留下的庞大遗产中,包括广阔的土地。 这片土地呈矩形,南北延伸$H$公里,东西向$W公里。 该土地以1平方公里为单位管理, 在北端$i$至$i+1$、西端$j$至$j+1$范围内的1公里见方地块称为$(i, j)$地块。 ($i$ 和 $j$ 是满足 $0 \leq i < H$ 和 $0 \leq j < W$ 的整数。) 土地价格为每个地块确定,地块$(i, j)$的价格表示为$a_{i, j}$。

兄弟们决定分割土地并继承如下。

  • $N$ 每个兄弟选择几个地块继承。
  • 各兄弟继承的土地必须选择成一个长方形。
  • $N$ 个兄弟继承的土地不得重叠。
  • 允许存在无人继承的地块。无人继承的地块将被放弃。

一个继承人的土地价格被定义为其土地范围内所有地块价格的总和。 兄弟们希望尽量公平地划分土地,使每个人继承的土地价格接近。 你的任务是,考虑如何划分土地,使 $N$ 个兄弟中继承土地价格最低的人所继承的土地价格达到最大。 请编写程序,计算按照这种方式划分土地时,继承土地价格最低的人所继承的土地价格。


输入

输入将以如下格式给出。

$H$$W$$N$
$a_{0,0}$ $a_{0,1}$ ... $a_{0,W-1}$
...
$a_{H-1,0}$ $a_{H-1,1}$ ... $a_{H-1,W-1}$

$H$ 和 $W$ $(2 \leq H, W \leq 200)$ 分别代表遗产土地的南北走向和东西走向长度。 $N$$(2 \leq N \leq 4)$ 代表兄弟继承土地的季节。 $a_{i, j}$ $(0 \leq a_{i,j} \leq 10^4)$ 表示地块 $(i, j)$ 的价格。

输出

当将继承权最低者的土地价格分割以最大化土地价格时, 用一条线输出最低的土地价格。



示例输入 1

3 3 2
1 2 2
3 1 0
0 4 3

样本输入 1 的输出

7

最好按照图示进行分割。


示例输入 2

3 3 2
0 1 0
1 1 1
0 1 0

样本输入 2 的输出

1

示例输入 3

2 5 3
8 3 0 5 6
2 5 2 5 2

样本输入 3 的输出

11

示例输入 4

3 3 4
3 3 4
3 3 4
3 3 4

样本输入 4 的输出

7

示例输入 5

4 4 4
2 2 2 2
2 1 2 1
2 2 2 2
2 1 2 1

样本输入 5 的输出

7