/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は、H 行 W 列のグリッド状に区画されたイベント会場の照明担当です。各区画には明るさの値が設定されており、上から i 行目、左から j 列目の区画の明るさを G_{i,j} とします。なお、明るさの値は負になることもあります。
高橋君は会場内からちょうど1つの区画を選び、そこにスポットライトを設置します。上から r 行目、左から c 列目の区画 (r, c) にスポットライトを設置すると、区画 (r, c) 自身を含む r 行目のすべての区画、および区画 (r, c) 自身を含む c 列目のすべての区画が十字型に照らされます。
このとき、照らされた全区画の明るさの合計を、その設置場所の照明スコアと呼びます。ただし、区画 (r, c) は r 行目と c 列目の両方に属しますが、照明スコアの計算では明るさを1回だけ数えます。
すなわち、区画 (r, c) にスポットライトを設置したときの照明スコアは以下の式で求められます。
\sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c}
高橋君は照明スコアが最大となる区画にスポットライトを設置したいと考えています。
照明スコアの最大値を求めてください。
制約
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- -10^9 \leq G_{i,j} \leq 10^9
- 入力はすべて整数である
入力
H W
G_{1,1} G_{1,2} \ldots G_{1,W}
G_{2,1} G_{2,2} \ldots G_{2,W}
\vdots
G_{H,1} G_{H,2} \ldots G_{H,W}
- 1 行目には、グリッドの行数を表す H と列数を表す W が、スペース区切りで与えられる。
- 2 行目から H + 1 行目では、グリッドの各行の値がスペース区切りで与えられる。
- 1 + i 行目には、i 行目の区画の明るさ G_{i,1}, G_{i,2}, \ldots, G_{i,W} がスペース区切りで与えられる。
出力
照明スコアの最大値を1行で出力せよ。
入力例 1
3 3 1 2 3 4 5 6 7 8 9
出力例 1
33
入力例 2
2 3 -1 -2 -3 -4 -5 -6
出力例 2
-10
入力例 3
4 5 3 -1 4 1 5 9 2 -6 5 3 -5 8 7 -2 4 6 0 -3 9 1
出力例 3
30
入力例 4
6 7 10 -3 5 8 -2 7 1 -4 6 9 -1 3 0 12 7 2 -8 4 11 -5 6 1 -6 3 15 -7 8 2 0 9 -4 6 3 -1 5 -3 4 7 -2 8 10 -6
出力例 4
56
入力例 5
1 1 -1000000000
出力例 5
-1000000000
Score : 333 pts
Problem Statement
Takahashi is in charge of lighting at an event venue partitioned into a grid with H rows and W columns. Each cell has a brightness value, and the brightness of the cell at the i-th row from the top and j-th column from the left is G_{i,j}. Note that the brightness values can be negative.
Takahashi will choose exactly one cell in the venue to install a spotlight. If he installs a spotlight at cell (r, c), located at the r-th row from the top and c-th column from the left, all cells in the r-th row (including cell (r, c) itself) and all cells in the c-th column (including cell (r, c) itself) will be illuminated in a cross shape.
The total brightness of all illuminated cells is called the lighting score of that installation location. Although cell (r, c) belongs to both the r-th row and the c-th column, its brightness is counted only once in the calculation of the lighting score.
That is, the lighting score when a spotlight is installed at cell (r, c) is given by the following formula:
\sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c}
Takahashi wants to install the spotlight at a cell that maximizes the lighting score.
Find the maximum possible lighting score.
Constraints
- 1 \leq H \leq 2000
- 1 \leq W \leq 2000
- -10^9 \leq G_{i,j} \leq 10^9
- All input values are integers.
Input
H W
G_{1,1} G_{1,2} \ldots G_{1,W}
G_{2,1} G_{2,2} \ldots G_{2,W}
\vdots
G_{H,1} G_{H,2} \ldots G_{H,W}
- The first line contains H, the number of rows of the grid, and W, the number of columns, separated by a space.
- The second through (H + 1)-th lines give the values of each row of the grid, separated by spaces.
- The (1 + i)-th line contains the brightness values of the cells in the i-th row, G_{i,1}, G_{i,2}, \ldots, G_{i,W}, separated by spaces.
Output
Print the maximum lighting score in a single line.
Sample Input 1
3 3 1 2 3 4 5 6 7 8 9
Sample Output 1
33
Sample Input 2
2 3 -1 -2 -3 -4 -5 -6
Sample Output 2
-10
Sample Input 3
4 5 3 -1 4 1 5 9 2 -6 5 3 -5 8 7 -2 4 6 0 -3 9 1
Sample Output 3
30
Sample Input 4
6 7 10 -3 5 8 -2 7 1 -4 6 9 -1 3 0 12 7 2 -8 4 11 -5 6 1 -6 3 15 -7 8 2 0 9 -4 6 3 -1 5 -3 4 7 -2 8 10 -6
Sample Output 4
56
Sample Input 5
1 1 -1000000000
Sample Output 5
-1000000000