巧克力蛋糕
测试数据来自 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
- 通过率
- ?
- 上传者