#2367. 「BalticOI 2008」网格

内存限制:32 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

题目译自 BalticOI 2008 Day2「Grid

Byteland 国的地图是一个大小为 n\times m 的网格( n 是垂直方向长度, m 是水平方向长度)。标记分隔的水平线被叫做平行线,并编号为 0 n ,标记分隔的垂直线被叫做子午线,并编号为 0 m
在 Byteland 国,天气预报是一个十分严肃的话题,对于每个单元格,准备天气预报需要一定时间来计算。由于地形条件和其他因素,不同的单元格有着不同的计算时间。直到目前为止,预报系统还是会依次处理每一个单元格,所以完成预报天气需要花费的时间为计算所有单元的时间。

你被要求设计一个可以在多进程处理器上运行的新系统,为了共享处理器的计算能力,Byteland 国要被 r 条平行线和 s 条子午线划分为 (r+1)(s+1) 个矩形。每个线程会依次处理一个矩形内部的单元格,这样的话对于一个矩形区域的计算时间,就为矩形区域内单元格计算时间之和。完成预报的计算时间是一个处理器上计算时间的最大值。
你的任务是找到对于选择 r 条平行线和 s 条子午线分隔后最小的计算时间。

任务

写一个程序能够:

  • 从标准输入读取 Byteland 的地图,要求的平行线和子午线条数以及每个单元格的处理时间;
  • 找到完成预报的最小计算时间;
  • 输出这个值到标准输出。

输入格式

第一行包含四个正整数 n,m,r,s ,由一个空格隔开。
接下来 n 行包含每一个单元格的计算时间 c_{i,j} 。第 i+1 行的第 j 个数表示位于第 i-1 和第 i 条平行线,第 j-1 和第 j 条子午线之间的单元格需要的计算时间。

输出格式

输出一行一个整数,表示最优的计算时间。

样例

样例输入

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

样例解释

p.png

第二条和第四条平行线,第四条子午线把整个国家分为六个矩形,计算时间为 21, 13, 27, 27, 17, 31 ,所以完成预报的计算时间为 31

数据范围与提示

对于 40\% 的数据, n\le 10,m\le 10
对于全部数据, 1\le r<n\le 18,1\le s<m\le 18 1\le i\le n,1\le j\le m,0\le c_{i,j}\le 2\times 10^6