Score : $600$ points

问题描述

我们有一个矩形蛋糕。它被划分为 $H$ 行和 $W$ 列的区域，且在从上数第 $i$ 行、从左数第 $j$ 列的区域内有 $s_{i,j}$ 个草莓。

你将进行 $T$ 次切割，将其分割成 $T+1$ 块。每次切割将按照以下两种方式进行之一：

• 选择一块包含两行或多行区域的现有蛋糕片。另外，在这块蛋糕片中选择相邻的两行，并沿着这两行之间的边界切割，将其分成两个更小的蛋糕片。
• 选择一块包含两列或多列区域的现有蛋糕片。另外，在这块蛋糕片中选择相邻的两列，并沿着这两列之间的边界切割，将其分成两个更小的蛋糕片。

你希望尽可能均匀地分配草莓到得到的蛋糕片上。
设 $x_1, x_2, \ldots, x_{T+1}$ 分别为最终得到的 $T+1$ 块蛋糕上的草莓数量，其中 $M$ 和 $m$ 分别表示这些数量中的最大值和最小值。求解最小可能的 $M-m$ 值。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a rectangular cake. It is partitioned into $H$ rows and $W$ columns of sections, and the section at the $i$-th row from the top and $j$-th column from the left has $s_{i,j}$ strawberries on it.

You will make $T$ cuts to divide the cake into $T+1$ pieces. Each cut will be done in one of the following two manners.

• Choose an existing piece with two or more rows of sections. Additionally, choose two adjacent rows from that piece, and cut the piece along the boundary between them to divide it into two smaller pieces.
• Choose an existing piece with two or more columns of sections. Additionally, choose two adjacent columns from that piece, and cut the piece along the boundary between them to divide it into two smaller pieces.

You want to distribute the strawberries onto the resulting pieces as evenly as possible.
Let $x_1,x_2,\ldots,x_{T+1}$ be the numbers of strawberries on the resulting $T+1$ pieces, and $M$ and $m$ be the maximum and minimum among those numbers, respectively. Find the minimum possible value of $M－m$.

Constraints

• $1 \leq H,W \leq 6$
• $1 \leq T \leq HW-1$
• $0 \leq s_{i,j} \leq 10^{16}$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $T$

$s_{1,1}$ $\ldots$ $s_{1,W}$

$\vdots$

$s_{H,1}$ $\ldots$ $s_{H,W}$

Output

Print the answer.

Sample Input 1

2 3 4
2 3 4
4 1 3

Sample Output 1

2

The figure below shows a way to cut the cake so that the top-left, bottom-left, middle, top-right, and bottom-right pieces have $2$, $4$, $4$, $4$, and $3$ strawberries on them, respectively. Here, the difference between the maximum and minimum number of strawberries is $4-2=2$. It is impossible to achieve a smaller difference, so the answer is $2$.

Sample Input 2

2 2 3
0 0
0 0

Sample Output 2

0

update @ 2024/3/10 12:23:14