#1401. [WJOI2021 小学组 H] 最高产量

[WJOI2021 小学组 H] 最高产量

题目描述

插秧了!我下了地里,学着爷爷的样子,分开两条腿,弓着腰,把秧苗对准前面的秧苗,插到田里去。“嘿,我成功了!”看到自己插的第一株秧苗,心里别提多高兴了。于是,我照着前面的方法,插了一株又一株,一股自豪感涌上我的心头。不一会儿,我插的一小块田就成了一小片 “草原”,在风中摇摇拽拽,仿佛一位亭亭玉立的美女子。

你们知道吗?秧苗长大了就成了水稻,水稻脱粒后就成了我们可以食用的大米。小周是一位刚入行的新手,这不,他插的秧苗稀稀落落。

他有一块 MMNN 列的秧田,也即最多可以插 MNM*N 株秧苗。因为没有经验,有一些地方没有种植成功,现给出每个位置是否成功的数据,其中 1 表示成功,0 表示失败。 虽然小周是位新手,但他有一种超能力是别人不具备的,他可以选择任一行或列,转换该行或列中的每一个值:将所有 0 都更改为 1,将所有 1 都更改为 0

在做出任意次数的变换后,小周发现有好多秧苗“活”过来了,当然也有一些“死”去了,这个超能力是把双刃剑啊。

现在的问题是,我们把每一行水稻的产量计算为这一行的 01 组成的二进制值,所有行的产量之和即这块田的水稻产量,试问变换所能达成的最高产量是多少?

题后记:超能力纯属玄幻之说,提高产量还是要相信科学,要依靠像袁隆平这样的将一生奉献给黄土地的科学家,向袁隆平老爷爷致敬!

输入格式

第一行:MMNN,表示秧田有 MMNN 列。

接下来 MM 行,每行 NN 个数 Ai,jA_{i,j}Ai,jA_{i,j} 要么为 00,要么为 11

输出格式

一个整数,表示能获得的最高产量。

3 4
1 1 1 1
1 0 1 0
1 1 0 0
38

样例解释

对第 44 列施展超能力。

数据范围

10%10\% 的数据:M=1M = 1

100%100\% 的数据:1M,N201 \le M,N \le 20