Skip to content

1408: 离岸政策

题目

题目描述

方块大陆由 $n\times m$ 块正方形区块作为最小单元构成,每个区块上都生活着或多或少的方块居民,有着不同的资源,因此也有着不同的地区实力。

Circle 国王在攻占了方块大陆后,意识到由自己直接管辖这片大陆不是一个很好的方案,这十分的消耗人力物力财力。于是他决定在这片大陆上扶植一个共同体,名字为“方块联盟”。为了让这片大陆上的人和睦相处~~也为了巩固自己的统治~~,Circle 国王决定将这片大陆以方块人喜欢的方式切割成多个国家。他先将这片大陆以横线划分成 $a$ 块,再用竖线分别将每块分割成 $b$ 块,形成 $a\times b$ 个国家。同时,为了防止出现一国独大而影响了公平~~统治与搅屎~~,他还希望能让国力(所包含的所有区块的地区实力之和)最弱小的国家的国力尽可能的强。因此,他想知道国力最弱的国家的国力可能的最大值是多少。

分割样例:

```text 1 2 | 2 1


3 | 1 1 1

2 0 1 | 3

1 1 | 1 1 1 1 | 1 1 ```

输入格式

第一行的输入 $n,m,a,b$

对于接下来的 $n$ 行的输入,每行输入 $m$ 个数,代表一个区块的地区实力 $p$ 。

输出格式

仅一行,输出国力最弱的国家的国力可能的最大值 $ans$

样例输入

text 5 4 4 2 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1

样例输出

text 3

数据范围

对于 10% 的数据,$n,m\leq10$

对于 30% 的数据,$n,m\leq100$ ,$0\leq p\leq1$ ,$\Sigma\Sigma p_{ij}\leq 20$

对于 20% 的数据,$n,m\leq300$ ,$0\leq p\leq1$ ,$\Sigma\Sigma p_{ij}\leq 10000$

对于所有的数据有 $n,m\leq500$ ,$p\leq8000$, $1\leq a\leq n$, $1\leq b\leq m$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!