DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Swap and Matrix Multiplication

Back to problem

Editorial

Let S0S_0S0​ be the value before the operation. Suppose Ax,k=aA_{x,k}=aAx,k​=a and Bk,x=bB_{k,x}=bBk,x​=b are swapped, and let d=b−ad=b-ad=b−a. Then Ax,kA_{x,k}Ax,k​ increases by ddd, while Bk,xB_{k,x}Bk,x​ decreases by ddd.

Among the entries included in SSS, the total change strictly to the right of the diagonal in row xxx is

d∑j=x+1NBk,j,d\sum_{j=x+1}^{N}B_{k,j},dj=x+1∑N​Bk,j​,

and the total change strictly above the diagonal in column xxx is

−d∑i=1x−1Ai,k.-d\sum_{i=1}^{x-1}A_{i,k}.−di=1∑x−1​Ai,k​.

The diagonal entry does not change because the affected product Ax,kBk,x=abA_{x,k}B_{k,x}=abAx,k​Bk,x​=ab becomes ba=abba=ab. Hence,

Δx,k=(Bk,x−Ax,k)(∑j=x+1NBk,j−∑i=1x−1Ai,k).\Delta_{x,k}=(B_{k,x}-A_{x,k})\left(\sum_{j=x+1}^{N}B_{k,j}-\sum_{i=1}^{x-1}A_{i,k}\right).Δx,k​=(B

Define column prefix sums of AAA and row suffix sums of BBB by

Pi,k=∑r=1iAr,k,Qk,i=∑c=iNBk,c.P_{i,k}=\sum_{r=1}^{i}A_{r,k},\qquad Q_{k,i}=\sum_{c=i}^{N}B_{k,c}.Pi,k​=r=1

With P0,k=0P_{0,k}=0P0,k​=0 and Qk,N+1=0Q_{k,N+1}=0Qk,N+1​, each change is computed in as

Δx,k=(Bk,x−Ax,k)(Qk,x+1−Px−1,k).\Delta_{x,k}=(B_{k,x}-A_{x,k})(Q_{k,x+1}-P_{x-1,k}).Δx,k​=(Bk

The initial sum can also be computed without constructing the entire product by changing the order of summation:

S0=∑i=1N∑k=1NAi,kQk,i.S_0=\sum_{i=1}^{N}\sum_{k=1}^{N}A_{i,k}Q_{k,i}.S0​=i=1∑N​

Since performing no operation is allowed, the answer is

S0+max⁡(0,max⁡1≤x,k≤NΔx,k).S_0+\max\left(0,\max_{1\leq x,k\leq N}\Delta_{x,k}\right).S0​+max(0,1≤x,k≤

Both the time and space complexities are O(N2)O(N^2)O(N2).

Solution written by GPT6

ba=
ab
k,x​
−
Ax,k​)(j=x+1∑N​Bk,j​−i=1∑x−1​Ai,k​).
∑
i
​
Ar,k​
,
Qk,i​
=
c=i∑N​Bk,c​.
=
0
O(1)O(1)O(1)
,
x
​
−
Ax,k​)(Qk,x+1​−
Px−1,k​).
k=1∑N​
Ai,k​
Qk,i​
.
N
max
​
Δx,k​
)
.