Overview

Given an \(H \times W\) grid, this problem asks us to find the maximum sum of brightness in the cross-shaped region illuminated by a spotlight placed at a cell (referred to as the illumination score).

Analysis

A naive approach would be to directly calculate the illumination score for each cell \((i, j)\). The illumination score can be calculated as the sum of the \(i\)-th row plus the sum of the \(j\)-th column minus the value at \((i, j)\) which is double-counted (\(\sum_{k=1}^{W} G_{i,k} + \sum_{k=1}^{H} G_{k,j} - G_{i,j}\)). However, if we recalculate the row and column sums for every cell from scratch, the time complexity becomes \(O(HW \times (H + W))\). When \(H\) and \(W\) are at most 2000, this requires \(2000 \times 2000 \times (2000 + 2000) = 16 \times 10^9\) operations, which will not finish within the time limit.

Therefore, by precomputing the row sums and column sums in advance, we can calculate the illumination score for each cell in constant time. This reduces the overall time complexity to \(O(HW)\).

Algorithm

1. Read the input and store the grid as a 2D list.
2. Prepare an array row_sums of length \(H\) to store the sum of each row, and an array col_sums of length \(W\) to store the sum of each column.
3. Traverse the grid and accumulate the sum of the \(i\)-th row into row_sums[i] and the sum of the \(j\)-th column into col_sums[j].
4. For every cell \((i, j)\), calculate the illumination score as row_sums[i] + col_sums[j] - grid[i][j], and update the maximum value.
5. Output the maximum value.

Complexity

• Time Complexity: \(O(HW)\)
  • The nested loop to calculate the row and column sums takes \(O(HW)\) time.
  • The nested loop to compute the illumination score for each cell takes \(O(HW)\) time.
• Space Complexity: \(O(HW)\)
  • Storing the grid requires \(O(HW)\) space.
  • The arrays for row sums and column sums require \(O(H + W)\) space.

Implementation Details

• Precomputing the row and column sums allows each cell’s illumination score to be calculated in constant time.

• Since the illumination score can be negative, initialize the answer variable to a sufficiently small value (such as \(-10^{18}\)).

• Even for large inputs (\(H\) and \(W\) up to 2000, \(G_{i,j}\) up to \(10^9\)), Python handles large integers automatically without overflow issues.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        return
    
    H = int(data[0])
    W = int(data[1])
    grid = []
    index = 2
    for i in range(H):
        row = list(map(int, data[index:index+W]))
        index += W
        grid.append(row)
    
    row_sums = [0] * H
    col_sums = [0] * W
    
    for i in range(H):
        for j in range(W):
            row_sums[i] += grid[i][j]
            col_sums[j] += grid[i][j]
    
    ans = -10**18
    for i in range(H):
        for j in range(W):
            total = row_sums[i] + col_sums[j] - grid[i][j]
            if total > ans:
                ans = total
                
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.1.