bzoj#P1169. [Baltic2008]Grid
[Baltic2008]Grid
题目描述
给出一个 行 列的矩阵。你可以横着切 刀,竖着切 刀将它分成小的矩阵。现在希望每个小矩阵的总和,最大的那个最小化。
输入格式
第一行给出 。
下面 行 列给出矩阵。
输出格式
总和最大的那个矩阵,其值最小可以为多少。
7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0
31
样例说明
从第二行、第四行下边、第四列右边把矩阵切开,所得的六个矩阵的和分别为 。可以证明没有比 更小的答案。
数据规模与约定
对于 的数据,。