102596: [AtCoder]ABC259 G - Grid Card Game
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
There are $H \times W$ cards on a grid of squares with $H$ rows and $W$ columns. For each pair of integers $(i, j)$ such that $1 \leq i \leq H, 1 \leq j \leq W$, the card at the $i$-th row and $j$-th column has an integer $A_{i, j}$ written on it.
Takahashi and Aoki will cooperate to play a game, which consists of the following steps.
- First, Takahashi chooses some of the $H$ rows (possibly none or all) and places a red token on each card in the chosen rows.
- Second, Aoki chooses some of the $W$ columns (possibly none or all) and places a blue token on each card in the chosen columns.
- Now, they compute their score as follows.
- If there is a card with a negative integer that has both red and blue tokens placed on it, the play is a "total failure"; the score is $-10^{100}$.
- Otherwise, they collect all cards that have one or more tokens placed on them. The score is the sum of the integers written on the collected cards.
Find their maximum possible score.
Constraints
- $1 \leq H, W \leq 100$
- $-10^9 \leq A_{i, j} \leq 10^9$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$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}$
Output
Print the answer.
Sample Input 1
2 3 -9 5 1 6 -2 4
Sample Output 1
9
If Takahashi chooses just the $2$-nd row and Aoki chooses just the $3$-rd column, they collect four cards, for a score of $6 + (-2) + 1 + 4 = 9$. This is the maximum possible.
Sample Input 2
15 20 -14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16 14 31 43 -73 49 -7 -65 13 -40 -45 36 88 -54 -43 99 87 -94 57 -22 31 -85 67 -46 23 95 68 55 17 -56 51 -38 64 32 -19 65 -62 76 66 -53 -16 35 -78 -41 35 -51 -85 24 -22 45 -53 82 -30 39 19 -52 -3 -11 -67 -33 71 -75 45 -80 -42 -31 94 59 -58 39 -26 -94 -60 98 -1 21 25 0 -86 37 4 -41 66 -53 -55 55 98 23 33 -3 -27 7 -53 -64 68 -33 -8 -99 -15 50 40 66 53 -65 5 -49 81 45 1 33 19 0 20 -46 -82 14 -15 -13 -65 68 -65 50 -66 63 -71 84 51 -91 45 100 76 -7 -55 45 -72 18 40 -42 73 69 -36 59 -65 -30 89 -10 43 7 72 93 -70 23 86 81 16 25 -63 73 16 34 -62 22 -88 27 -69 82 -54 -92 32 -72 -95 28 -25 28 -55 97 87 91 17 21 -95 62 39 -65 -16 -84 51 62 -44 -60 -70 8 69 -7 74 79 -12 62 -86 6 -60 -72 -6 -79 -28 39 -42 -80 -17 -95 -28 -66 66 36 86 -68 91 -23 70 58 2 -19 -20 77 0 65 -94 -30 76 55 57 -8 59 -43 -6 -15 -83 8 29 16 34 79 40 86 -92 88 -70 -94 -21 50 -3 -42 -35 -79 91 96 -87 -93 -6 46 27 -94 -49 71 37 91 47 97 1 21 32 -100 -4 -78 -47 -36 -84 -61 86 -51 -9
Sample Output 2
1743
Input
题意翻译
芷萱和诺丝正在玩一个有趣的游戏。 有一个 $H \times W$ 的正方形网格，$i$ 行 $j$ 列的点的权值为 $a_{i,j}$。 + 芷萱选择 $H$ 行中的任意几行（可能为 $0$），给这些行上的点放上一张红色卡片。 + 诺丝选择 $W$ 列中的任意几列（可能为 $0$），给这些列上的点放上一张蓝色卡片。 他们计算本游戏分数的方式如下： 如果存在一个网格 $(i,j)$ 满足 $a_{i,j}<0$ 且这个点上同时存在两种颜色的卡片，则游戏失败，分数为 $-10100$ 分，否则，分数为所有放了卡片（不管放了几张，不管放了什么颜色）的网格的权值之和。 Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)Output
分数：600分
问题描述
在一个由H行W列的正方形组成的网格上有H×W张卡片。对于每一对整数$(i, j)$，使得$1 \leq i \leq H, 1 \leq j \leq W$，第i行第j列的卡片上写有一个整数$A_{i, j}$。
高桥和青木将合作玩一个游戏，游戏包括以下步骤。
- 首先，高桥从H行中选择任意一些（可能一行都不选，也可能全选）并在所选行中的每张卡片上放置一个红色标记。
- 其次，青木从W列中选择任意一些（可能一列都不选，也可能全选）并在所选列中的每张卡片上放置一个蓝色标记。
- 现在，他们根据以下规则计算得分。
- 如果有一张卡片上有负整数并且放置了红色和蓝色标记，那么游戏是“彻底失败”，得分为$-10^{100}$。
- 否则，他们收集所有放置了一个或多个标记的卡片。得分是所收集卡片上写的整数之和。
找到他们的最高可能得分。
限制条件
- $1 \leq H, W \leq 100$
- $-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}$
输出
打印答案。
样例输入1
2 3 -9 5 1 6 -2 4
样例输出1
9
如果高桥只选择第2行，青木只选择第3列，他们将收集到4张卡片，得分为$6 + (-2) + 1 + 4 = 9$。 这是可能的最高得分。
样例输入2
15 20 -14 74 -48 38 -51 43 5 37 -39 -29 80 -44 -55 59 17 89 -37 -68 38 -16 14 31 43 -73 49 -7 -65 13 -40 -45 36 88 -54 -43 99 87 -94 57 -22 31 -85 67 -46 23 95 68 55 17 -56 51 -38 64 32 -19 65 -62 76 66 -53 -16 35 -78 -41 35 -51 -85 24 -22 45 -53 82 -30 39 19 -52 -3 -11 -67 -33 71 -75 45 -80 -42 -31 94 59 -58 39 -26 -94 -60 98 -1 21 25 0 -86 37 4 -41 66 -53 -55 55 98 23 33 -3 -27 7 -53 -64 68 -33 -8 -99 -15 50 40 66 53 -65 5 -49 81 45 1 33 19 0 20 -46 -82 14 -15 -13 -65 68 -65 50 -66 63 -71 84 51 -91 45 100 76 -7 -55 45 -72 18 40 -42 73 69 -36 59 -65 -30 89 -10 43 7 72 93 -70 23 86 81 16 25 -63 73 16 34 -62 22 -88 27 -69 82 -54 -92 32 -72 -95 28 -25 28 -55 97 87 91 17 21 -95 62 39 -65 -16 -84 51 62 -44 -60 -70 8 69 -7 74 79 -12 62 -86 6 -60 -72 -6 -79 -28 39 -42 -80 -17 -95 -28 -66 66 36 86 -68 91 -23 70 58 2 -19 -20 77 0 65 -94 -30 76 55 57 -8 59 -43 -6 -15 -83 8 29 16 34 79 40 86 -92 88 -70 -94 -21 50 -3 -42 -35 -79 91 96 -87 -93 -6 46 27 -94 -49 71 37 91 47 97 1 21 32 -100 -4 -78 -47 -36 -84 -61 86 -51 -9
样例输出2
1743