Overview

This problem asks us to efficiently compute “(sum of the row) + (sum of the column) - (cell itself)” when placing a spotlight at each cell \((r,c)\), and find the maximum value.

Analysis

The lighting score when placing a spotlight at \((r,c)\) is
\(\sum_{j=1}^{W} G_{r,j} + \sum_{i=1}^{H} G_{i,c} - G_{r,c}\).
The key insight here is that this can be decomposed as follows:

• \(\sum_{j=1}^{W} G_{r,j}\) is the “sum of row \(r\)”
• \(\sum_{i=1}^{H} G_{i,c}\) is the “sum of column \(c\)”
• \(G_{r,c}\) is added twice (once in the row sum and once in the column sum), so we subtract it once.

Why a Naive Approach is Too Slow

If we sum \(W\) elements horizontally and \(H\) elements vertically for each cell \((r,c)\) every time: - Per cell: \(O(H+W)\) - For all cells: \(O(HW(H+W))\)

Since the constraints are \(H,W \le 2000\), \(HW = 4\times 10^6\) in the worst case. Multiplying this by \((H+W)\approx 4000\) will result in Time Limit Exceeded (TLE).

Solution

If we precalculate: - Sum of each row row[r] - Sum of each column col[c]

in \(O(HW)\) time, the score for any cell \((r,c)\) can be computed in \(O(1)\) time as:

\(score(r,c)=row[r]+col[c]-G_{r,c}\)

Then, we just need to iterate through all cells and find the maximum value.

Algorithm

1. While reading the input, accumulate the row sums and column sums into arrays row and col respectively.
   At the same time, store all elements in a 1D array a so that we can refer to \(G_{r,c}\) later.
2. For all cells \((r,c)\):
   • Compute \(val = row[r] + col[c] - G_{r,c}\) and update the maximum value.
3. Output the maximum value.

(Example)
If the row sum is row[r]=10, column sum is col[c]=7, and the intersection is G[r][c]=3, then
\(10+7-3=14\) is the lighting score.

Complexity

• Time Complexity: \(O(HW)\)
• Space Complexity: \(O(HW + H + W)\)

Implementation Details

• 64-bit Integers Required: The sum can reach up to \(2000 \times 10^9 = 2\times 10^{12}\), which overflows a 32-bit integer. Python’s int handles arbitrarily large integers automatically, but storage arrays should assume 64-bit types in standard languages.

• Memory Optimization: Since \(HW\) can be up to \(4\times 10^6\), placing standard Python int objects into a standard list consumes a large amount of memory. In the code, memory consumption is reduced by using array('q') (64-bit signed integer array) to store G.

• Fast I/O: Since there are up to 4 million elements, using sys.stdin.buffer.read() to read all inputs at once and parsing them with a custom integer parser speeds up the input processing.

  Source Code

import sys
from array import array

def int_stream():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            return
        sign = 1
        if data[i] == 45:  # '-'
            sign = -1
            i += 1
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield sign * num

it = int_stream()
H = next(it)
W = next(it)

row = [0] * H
col = [0] * W

N = H * W
a = array('q', [0]) * N

for r in range(H):
    base = r * W
    s = 0
    for c in range(W):
        v = next(it)
        a[base + c] = v
        s += v
        col[c] += v
    row[r] = s

col_local = col
a_local = a
ans = -10**30

for r in range(H):
    base = r * W
    rs = row[r]
    for c in range(W):
        val = rs + col_local[c] - a_local[base + c]
        if val > ans:
            ans = val

print(ans)

---

This editorial was generated by gpt-5.2-high.