分数: 433 分
问题陈述
高桥有一个网格 H 行和 W 列。牢房位于 i从顶部算起的第行 (1 \leq i \leq H) 和 j左起第 列 (1 \leq j \leq W) 表示为 (i, j)。细胞的价值 (i, j) 是整数 A_{i,j}.
Takahashi 自由选择一组行 R \subseteq \{1, 2, \ldots, H\} 和一组列 C \subseteq \{1, 2, \ldots, W\}。每一个 R 和 C 可能是空集。
一个单元格 (i, j) is 涂漆 如果至少其中之一 i \in R or j \in C 成立。让 S 是所绘制单元格的值的总和。也就是说,
S = \sum_{\substack{(i,j) \\ i \in R \text{ or } j \in C}} A_{i,j}
如果没有绘制任何单元格(即 R = C = \emptyset),然后 S = 0.
找到最大值 S 所有可能的选择 R 和 C.
> 注意(使用包含排除原理的等效表达式): 以上 S 也可以如下计算。
>
> S = \sum_{i \in R} \sum_{j=1}^{W} A_{i,j} + \sum_{j \in C} \sum_{i=1}^{H} A_{i,j} - \sum_{i \in R} \sum_{j \in C} A_{i,j}
约束
- 1 \leq H \leq 19
- 1 \leq W \leq 19
- -10^9 \leq A_{i,j} \leq 10^9
- 所有输入值均为整数。
输入
输入按以下格式给出。
H W
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
第一行包含行数 H 和列数 网格的 W 。以下 H 行包含值 每个单元格的 A_{i,j} ,用空格分隔。
输出
打印最大值 S 在一行中。
示例输入 1
2 3 5 -2 4 -3 6 -1
示例输出 1
13
示例输入 2
3 3 -1 -2 -3 -4 -5 -6 -7 -8 -9
示例输出 2
0
示例输入 3
5 6 3 -5 2 7 -1 4 -4 6 -2 1 8 -3 5 -3 0 -6 4 2 -7 2 9 -1 -5 6 1 -8 3 5 -2 7
示例输出 3
50
示例输入 4
8 8 1000000000 -1000000000 5 -7 8 -9 10 -11 -1000000000 1000000000 -6 7 -8 9 -10 12 13 -14 1000000000 -1000000000 15 -16 17 -18 -19 20 -1000000000 1000000000 -21 22 -23 24 25 -26 27 -28 1000000000 -1000000000 29 -30 -31 32 -33 34 -1000000000 1000000000 -35 36 37 -38 39 -40 41 -42 1000000000 -1000000000 -43 44 -45 46 -47 48 -1000000000 1000000000
示例输出 4
4000000321
示例输入 5
1 1 1000000000
示例输出 5
1000000000