cswork / OA打开练习工作台

AmazonOA #26

Find Max Greyness

估计中等可在线判题

考点(AI 标注)原地数组前缀和区间

The grayness of cell (i,j) equals the total number of 1s minus the total number of 0s in its row and its column; the intersection cell is counted once in the row and once in the column. Find the maximum grayness.

Conventions marked as this site's do not pass themselves off as the source's original limits.

输入格式

The first line contains n m (both 1..1000), followed by n lines of 01 strings of length m.

输出格式

Output a single integer, the answer.

样例 1

输入:

3 3
101
001
110

输出:

2

样例 2

输入:

1 1
0

输出:

-2

样例 3

输入:

2 2
11
11

输出:

4

样例说明

Example 1: the first row and the first column each have two 1s and one 0, so the grayness is (2+2)−(1+1)=2. Example 2: the only 0 is counted once in its row and once in its column, so the grayness is −2. Example 3: every row and column has two 1s, so the maximum grayness is 4.