AT_abc298_g [ABC298G] Strawberry War

题目描述

有一个长方形的蛋糕。这个蛋糕被分成 $H$ 行 $W$ 列的格子，从上往下第 $i$ 行，从左往右第 $j$ 列的格子上有 $s_{i,j}$ 个草莓。

你需要进行 $T$ 次切割操作，将蛋糕分成 $T+1$ 块。每次切割可以按以下两种方式之一进行：

• 选择一个当前存在的蛋糕块，且该块的行数不少于 $2$。然后选择该蛋糕块中相邻的两行，在它们之间切一刀，将蛋糕块分成两块更小的蛋糕。
• 选择一个当前存在的蛋糕块，且该块的列数不少于 $2$。然后选择该蛋糕块中相邻的两列，在它们之间切一刀，将蛋糕块分成两块更小的蛋糕。

你的目标是使分割后的每块蛋糕上的草莓数量尽可能均匀。
设分割后 $T+1$ 块蛋糕上的草莓数量分别为 $x_1,x_2,\ldots,x_{T+1}$，其中最大值为 $M$，最小值为 $m$，请你求出 $M-m$ 的最小可能值。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

2 3 4
2 3 4
4 1 3

输出 #1

2

输入输出样例 #2

输入 #2

2 2 3
0 0
0 0

输出 #2

0

说明/提示

限制条件

• $1 \leq H, W \leq 6$
• $1 \leq T \leq HW-1$
• $0 \leq s_{i,j} \leq 10^{16}$
• 输入均为整数

样例解释 1

如下图所示进行切割后，左上角的蛋糕有 $2$ 个草莓，左下角有 $4$ 个草莓，中间的蛋糕有 $4$ 个草莓，右上角有 $4$ 个草莓，右下角有 $3$ 个草莓。此时草莓数量的最大值和最小值之差为 $4-2=2$，无法再更小，因此答案为 $2$。

由 ChatGPT 4.1 翻译