問題文に記載の計算式の通りに計算すると 1 マスあたり \(\Theta(H+W)\) 時間かかるため、全てのマスをこの通りに計算すると \(\Theta(HW(H+W))\) かかり、実行時間制限に間に合わせるのは困難です。

予め行の和、列の和を求めておきます。つまり

\(\mathrm{row}[i]=\sum_{j=1}^{W}G_{i,j}\)
\(\mathrm{col}[j]=\sum_{i=1}^{H}G_{i,j}\)

と定めます。これらは全ての \(i,j\) についてを \(O(HW)\) で求めることができます。

これらを予め計算しておくことで、マス \((i,j)\) の明るさは \(\mathrm{row}[i] + \mathrm{col}[j]-G_{i,j}\) と \(O(1)\) で計算することができるため、全体で \(O(HW)\) でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<int>> g(h, vector<int>(w));
  for(int i=0; i<h; i++)for(int j=0; j<w; j++) cin >> g[i][j];
  vector<long long> col(w),row(h);
  for(int i=0; i<h; i++)for(int j=0; j<w; j++){
    col[j] += g[i][j];
    row[i] += g[i][j];
  }
  
  long long ans = -1e18;
  for(int i=0; i<h; i++)for(int j=0; j<w; j++){
    ans = max(ans, col[j] + row[i] - g[i][j]);
  }
  cout << ans << endl;
}

実装例 (Python)

H, W = map(int, input().split())
G = [list(map(int, input().split())) for _ in range(H)]

col = [0] * W
row = [0] * H
for i in range(H):
  for j in range(W):
    col[j] += G[i][j]
    row[i] += G[i][j]

ans = -10**18
for i in range(H):
  for j in range(W):
    ans = max(ans, col[j] + row[i] - G[i][j])

print(ans)