巧克力蛋糕

巧克力蛋糕

测试数据来自 wjszez/2110

【问题描述】
有一块矩形的巧克力蛋糕,我们可以把它看成是R×C(1<=R,C<=500)个小网格,每个网格上有N_ij(0<=N_ij<=4,000)颗巧克力豆。
现在我们将这块蛋糕切成A×B(1<=A<=R,1<=B<=C)块。先沿水平方向切A-1刀(沿着网格线),得到A条蛋糕,然后对于每条蛋糕,独立的沿垂直方向切B-1刀(沿着网格线)。蛋糕切好后,很快就被分掉了,只留下最后一块给你。由于人人都爱吃巧克力豆,因此,每个人拿蛋糕的时候都会选择巧克力豆最多的那块。当然,你也想要吃到尽可能多的巧克力豆。
请你设计一个切蛋糕的方案,使得自己可以吃到尽可能多的巧克力豆。
【输入数据】
输入数据共若干行。第一行包含四个用空格隔开的整数R、C、A、B。接下来R行,每行包含C个用空格隔开的整数N_ij。
【输出数据】
输出数据仅一个整数,表示可能得到的最多巧克力豆的数量。
【样例】
brownie.in
5 4 4 2
1 2 2 1
3 1 1 1
2 0 1 3
1 1 1 1
1 1 1 1

brownie.out
3

【样例说明】

信息

ID
2518
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者