Overview

In an \(H \times W\) grid, placing a spotlight in a cell illuminates the entire row and column containing that cell. Find the placement location that maximizes the total brightness of the illuminated cells (lighting score).

Analysis

The lighting score when placing a spotlight at cell \((r, c)\) is given by:

\[ \sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c} \]

This represents “the sum of the \(r\)-th row” plus “the sum of the \(c\)-th column”, minus \(G_{r,c}\) which was counted twice.

If we naively compute this for all cells, we would need to recalculate the row sum and column sum every time. This results in a time complexity of \(O(H \cdot W \cdot (H + W))\), which will TLE given the constraints \(H, W \leq 2000\) (requiring up to around \(8 \times 10^9\) operations).

Therefore, by precomputing the sum of each row and each column in advance, we can calculate the lighting score for each spotlight placement location in \(O(1)\) time.

For example, let’s look at a small example:

\[ G = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \]

In this case: - Row sums: row_sums = [3, 7] - Column sums: col_sums = [4, 6]

If we place the spotlight at \((1,1)\) (or \((0,0)\) in 0-indexed): $\( \text{score} = 3 + 4 - 1 = 6 \)$

In this way, precomputing the sums allows us to find the solution efficiently.

Algorithm

1. Calculate the sum of each row and store them in the row_sums array.
2. Calculate the sum of each column and store them in the col_sums array.
3. For all cells \((i, j)\), calculate the lighting score row_sums[i] + col_sums[j] - G[i][j] and keep track of the maximum value.
4. Output the maximum value.

Complexity

• Time Complexity: \(O(H \cdot W)\)

• Space Complexity: \(O(H \cdot W)\)

• Note that reading the input and calculating the sums form the bottleneck, but overall it runs in linear time relative to the grid size.

Implementation Details

• sys.stdin.read is used to read the input quickly.

• Precomputing row_sums and col_sums speeds up the calculation during the full search.

• Since brightness values can be negative, initialize the maximum score variable with a sufficiently small value (e.g., float('-inf')).

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    H = int(data[0])
    W = int(data[1])
    G = []
    idx = 2
    for _ in range(H):
        row = list(map(int, data[idx:idx+W]))
        idx += W
        G.append(row)
    
    # 各行の合計
    row_sums = [sum(row) for row in G]
    
    # 各列の合計
    col_sums = [0] * W
    for j in range(W):
        for i in range(H):
            col_sums[j] += G[i][j]
    
    max_score = float('-inf')
    for i in range(H):
        for j in range(W):
            score = row_sums[i] + col_sums[j] - G[i][j]
            if score > max_score:
                max_score = score
    
    print(max_score)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.