← 返回题目列表

AtCoder · abc298_g

G. 草莓战争

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

分数: 600 点

问题陈述

我们有一个长方形的蛋糕。它被分为 H 行和 W 节的列,以及位于 i从顶部开始的第行和 j从左边算起第 s_{i,j} 草莓就可以了。

你将会 T 将蛋糕切成 T+1 件。每次切割都将以以下两种方式之一完成。

  • 选择具有两行或更多行部分的现有片段。此外,从该块中选择两个相邻的行,并沿着它们之间的边界切割该块,将其分成两个较小的块。
  • 选择包含两列或更多列部分的现有作品。此外,从该块中选择两个相邻的列,并沿着它们之间的边界切割该块,将其分成两个较小的块。

您希望将草莓尽可能均匀地分布到所得的碎片上。
让 x_1,x_2,\ldots,x_{T+1} 是结果上草莓的数量 T+1 件,以及 M 和 m 分别是这些数字中的最大值和最小值。找到最小可能值 M-m.

约束

  • 1 \leq H,W \leq 6
  • 1 \leq T \leq HW-1
  • 0 \leq s_{i,j} \leq 10^{16}
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

H W T
s_{1,1} \ldots s_{1,W}
\vdots
s_{H,1} \ldots s_{H,W}

输出

打印答案。


示例输入 1

2 3 4
2 3 4
4 1 3

示例输出 1

2

下图展示了切蛋糕的方法,使得左上角、左下角、中间、右上角和右下角的块都有 2, 4, 4, 4,和 3 分别在上面放草莓。这里,最大和最小草莓数量之差是 4-2=2。不可能达到更小的差异,所以答案是 2.


示例输入 2

2 2 3
0 0
0 0

示例输出 2

0