【C#】 AtCoder競プロ典型90問-004- TLEになる原因が分からない

AtCoder 競プロ典型90問 -004- Cross Sum

問題文
H 行 W 列のマス目があります。上から i (1≤i≤H) 行目、左から j (1≤j≤W) 列目にあるマス (i,j) には、整数 Aijが書かれています。すべてのマス (i,j) (1≤i≤H,1≤j≤W) について、以下の値を求めてください。

マス (i,j) と同じ行または同じ列にあるマス（自分自身を含む）に書かれている整数をすべて合計した値

制約
2≤H,W≤2000
1 ≤ Aij ≤ 99
入力は全て整数

入力

H W
A1,1 A1,2 ・・・ A1,W
A2,1 A2,2 ・・・ A2,W
 ：
AH,1 AH,2 ・・・ AH,W

出力

B1,1 B1,2 ・・・ B1,W
B2,1 B2,2 ・・・ B2,W
 ：
BH,1 BH,2 ・・・ BH,W

自分の回答

マス(i,j)ごとにi行の合計とj列の合計を計算すると、計算量はo(HW(H+W))となる。
これでは計算量がo(10^9)となり、計算量が膨大となるため、以下の方法で回答を作成した。
①前処理として、先にi行の合計及びj列の合計を求め、結果をメモする
②マス(i,j)の出力として(i行の合計値)+(j列の合計値)-(マス(i,j)の値)を計算
以上の処理を行うことで、計算量としてはo(HW)に抑えられる。
以上の考えのもと、以下のコードを作成した。

C#
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5namespace AtCoder
6{
7    class Problem
8    {
9        static void Main()
10        {
11            // Step1 入力を受け取る
12            // 整数H,Wを受け取る
13            var input = Console.ReadLine().Split(" ").Select(int.Parse).ToArray();
14            var H = input[0];
15            var W = input[1];
16
17            // H行W列の配列を受け取る
18            int[,] nums = new int[H,W];
19            for(int i = 0; i < H; i++)
20            {
21                var gyou = Console.ReadLine().Split().Select(int.Parse).ToArray();
22                for (int j = 0; j < W; j++)
23                {
24                    nums[i,j] = gyou[j];
25                }
26            }
27
28            // （前処理）１行ごと１列ごとに合計を求め、メモする
29            // 横方向の合計の計算メモを作成
30            int[] sumArrayH = new int[H];
31            // 縦方向の合計の計算メモを作成
32            int[] sumArrayW = new int[W];
33
34            // 縦方向と横方向の計算結果をメモに入力する
35            for (int i = 0; i < H; i++)
36            {
37                for (int j = 0; j < W; j++)
38                {
39                    sumArrayH[i] += nums[i,j];
40                    sumArrayW[j] += nums[i,j];
41                }
42            }
43
44            // Step3 マス(i,j)の計算を行い、結果を出力する
45            for (int i = 0; i < H; i++)
46            {
47                var sum = 0;
48                for (int j = 0; j < W; j++)
49                {
50                    sum = sumArrayH[i] + sumArrayW[j] - nums[i,j];
51                    Console.Write("{0} ", sum);
52                }
53                Console.WriteLine("");
54            }
55        }
56    }
57}