問題一覧 > 通常問題

No.957 Tree Planting

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 56
作問者 : ei1333333 / テスター : treeone
お気に入りにしたユーザー ProblemId : 3556 / 自分の提出
問題文最終更新日: 2019-12-19 16:25:14
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2019 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns, and a tree can be planted in each cell. Planting a tree in the cell at row $i$, column $j$ costs $G_{i,j}$ yen.

Also, if trees are planted in all cells of row $i$, you receive $R_i$ yen. Similarly, if trees are planted in all cells of column $j$, you receive $C_j$ yen.

Find the maximum profit. The profit is defined as the sum of the money received by satisfying the conditions minus the sum of the costs of planting trees.

Input

$H$ $W$
$G_{1,1}$ $G_{1,2}$ $\cdots$ $G_{1,W}$
$G_{2,1}$ $G_{2,2}$ $\cdots$ $G_{2,W}$
$:$
$G_{H,1}$ $G_{H,2}$ $\cdots$ $G_{H,W}$
$R_1$ $R_2$ $\cdots$ $R_H$
$C_1$ $C_2$ $\cdots$ $C_W$
  • $1 \leq H, W \leq 300$
  • $0 \leq G_{i,j}, R_{i}, C_{j} \leq 10^9$
  • All input values are integers.

Output

Output the answer in $1$ line.

Sample

Sample 1
Input
2 3
1 2 3
4 5 6
6 2
1 7 3
Output
2

Plant trees in the cells of row $1$ and column $2$. The result is $(6+7)-(1 + 2 + 3 + 5) = 2$ yen.

Sample 2
Input
3 1
3
1
4
1 5 9
2
Output
9

Plant trees in all cells. The result is $(1+5+9+2)-(3+1+4) = 9$ yen.

Sample 3
Input
1 1
100
50
49
Output
0

It is optimal not to plant any trees.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。