102986: [Atcoder]ABC298 G - Strawberry War

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $600$ points

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

Input

题意翻译

给定一个 $H\times W$ 的矩阵，对于每一部分，我们可以挑选相邻的行或列中间切一道，变成两个部分。将这个矩阵分成 $T+1$ 个部分，对于每个部分，权值为部分内元素的和。要求最小化最大值减最小值的差。 translated by 月。

Output

分数：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

Source/Category

加入题单

算法标签：