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

問題 競プロ典型90問 004 - Cross Sum 考察 全探索を考える あるAn,mに対してのBn,mを求める計算量を考えます。 計算量は同じ行と同じ列の数字を全て足すのでH+Wになります。 そして全てのAn,mに対してこの計算を行うのでH × W × (H+W)となって間に合いません。(制約内の最大値で考えると1.6*10^10になってしまう) 各行と列の合計を先に出して仕舞えば良いのでは 行と列の合計を先に求めることによって An,mがある行と列の合計を足してAn,mを引く計算をするだけでBn,mが求められる。 ソース H,W = map(int,input().split()) A = [[0]*W for i in range(H)] hSum = [0] * H vSum = [0] * W for i in range(H): workA = list(map(int,i