/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
長方形のケーキがあります。このケーキは H 行 W 列に並ぶ区画に分かれていて、上から i 行目、左から j 列目の区画にはイチゴが s_{i,j} 個載っています。
あなたは T 回の切断を行ってケーキを T+1 切れに分割することにしました。各回の切断は、次のいずれかの方法で行います。
- 現存するケーキであって、区画の行の数が 2 以上であるものを選ぶ。さらに、そのケーキから隣接する 2 行を選び、その境界でケーキを切断してより小さなケーキ 2 切れに分割する。
- 現存するケーキであって、区画の列の数が 2 以上であるものを選ぶ。さらに、そのケーキから隣接する 2 列を選び、その境界でケーキを切断してより小さなケーキ 2 切れに分割する。
あなたの目標は、分割後のケーキに載ったイチゴの数をできるだけ均等にすることです。
分割後の T+1 切れのケーキに載ったイチゴの個数を x_1,x_2,\ldots,x_{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
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