Overview

In an \(H \times W\) grid, when choosing a cell \((r, c)\), we want to maximize the sum of brightness over the entire \(r\)-th row and \(c\)-th column (where the intersection cell is counted only once).

Analysis

Understanding the Lighting Score Formula

The lighting score when placing a spotlight at cell \((r, c)\) is expressed by the following formula:

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

This represents “(sum of row \(r\))” + “(sum of column \(c\))” − “(value at intersection \((r,c)\) to subtract the double-counted amount)”.

Issues with a Naive Approach

If we calculate the sum of the row and the column from scratch for each \((r, c)\), it would take \(O(H + W)\) time per cell, resulting in an overall time complexity of \(O(H \times W \times (H + W))\). When \(H, W \leq 2000\), this requires around \(4000 \times 4 \times 10^6 = 1.6 \times 10^{10}\) operations, which will result in a TLE (Time Limit Exceeded).

Solution: Precomputation

Looking closely at the formula for the lighting score, \(\sum_{j=1}^{W} G_{r,j}\) depends only on row \(r\), and \(\sum_{i=1}^{H} G_{i,c}\) depends only on column \(c\). That is:

• Precompute the sum of each row \(\text{row\_sum}[i]\)
• Precompute the sum of each column \(\text{col\_sum}[j]\)

By doing so, the lighting score for each \((r, c)\) can be computed in \(O(1)\) time.

Algorithm

1. Read the input and store the grid \(G\).
2. Calculate the row sums \(\text{row\_sum}[i] = \sum_{j=1}^{W} G_{i,j}\).
3. Calculate the column sums \(\text{col\_sum}[j] = \sum_{i=1}^{H} G_{i,j}\).
4. For all \((i, j)\), calculate \(\text{score} = \text{row\_sum}[i] + \text{col\_sum}[j] - G_{i][j}\) and find the maximum value.

Concrete Example

For example, consider the following \(2 \times 3\) grid:

 1  2  3
 4  5  6

• \(\text{row\_sum} = [6, 15]\)
• \(\text{col\_sum} = [5, 7, 9]\)

If we choose cell \((2, 3)\): $\(\text{score} = 15 + 9 - 6 = 18\)$

This is the sum of the 2nd row (\(4+5+6=15\)) and the 3rd column (\(3+6=9\)), minus the value at the intersection (\(6\)) subtracted once.

Complexity

• Time Complexity: \(O(H \times W)\) (\(O(H \times W)\) for precomputation, \(O(H \times W)\) for full search)
• Space Complexity: \(O(H \times W)\) (Required to store the grid; row and column sum arrays take \(O(H + W)\))

Implementation Points

• Watch out for integer overflow: Since the absolute value of \(G_{i,j}\) can be up to \(10^9\) and the length of a row or column can be up to 2000, the sum can reach around \(2 \times 10^{12}\). This is not an issue in Python since integers do not overflow, but languages like C++ require using long long.

• Fast I/O: In Python, reading the entire input at once using sys.stdin.buffer.read() helps alleviate input bottlenecks.

• Initial value: Setting the initial value of the answer to -float('inf') ensures correct behavior even when all values are negative.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    H = int(input_data[idx]); idx += 1
    W = int(input_data[idx]); idx += 1
    
    row_sum = [0] * H
    col_sum = [0] * W
    G = []
    
    for i in range(H):
        row = []
        s = 0
        for j in range(W):
            v = int(input_data[idx]); idx += 1
            row.append(v)
            s += v
            col_sum[j] += v
        row_sum[i] = s
        G.append(row)
    
    ans = -float('inf')
    for i in range(H):
        for j in range(W):
            score = row_sum[i] + col_sum[j] - G[i][j]
            if score > ans:
                ans = score
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.