Strawberry War

题目描述

我们有一个矩形蛋糕。它被划分为 $H$ 行 $W$ 列的格子，位于从上数第 $i$ 行、从左数第 $j$ 列的格子上有 $s_{i,j}$ 个草莓。 你将进行 $T$ 次切割以把蛋糕分成 $T+1$ 块。每次切割将以以下两种方式之一进行。

选择一个现有的、包含两行或以上格子的块。此外，从该块中选择两行相邻的行，并沿它们之间的边界切开该块，使其分成两个更小的块。 选择一个现有的、包含两列或以上格子的块。此外，从该块中选择两列相邻的列，并沿它们之间的边界切开该块，使其分成两个更小的块。

你想尽可能均匀地把草莓分布到得到的各块上。
令 $x_1,x_2,\ldots,x_{T+1}$ 为得到的 $T+1$ 块上的草莓数量，且令 $M$ 和 $m$ 分别为这些数中的最大值和最小值。求 $M－m$ 的最小可能值。

输入格式

输入由标准输入按如下格式给出： $H$ $W$ $T$ $s_{1,1}$ $\ldots$ $s_{1,W}$ $\vdots$ $s_{H,1}$ $\ldots$ $s_{H,W}$

输出格式

输出答案。

2 3 4
2 3 4
4 1 3

2

2 2 3
0 0
0 0

0

提示

$1 \leq H,W \leq 6$ $1 \leq T \leq HW-1$ $0 \leq s_{i,j} \leq 10^{16}$ 输入中的所有值均为整数。下图展示了一种切法，使得左上、左下、中间、右上和右下块上的草莓数分别为 $2$、$4$、$4$、$4$ 和 $3$。此时，最大值与最小值之差为 $4-2=2$。不可能得到更小的差值，因此答案为 $2$。

标签: AtCoder|abc298G

来源

AtCoder|abc298G