Max Trace (Editorial)

Solution

Claim. For n>2 matrix , It's possible to reorder the matrix into any matrix.

Consider rotating single 2 \times 2 submatrix , we can get all the $4$ distinct configuration of it ! , With the advantage of overlapping submatrices we can move elements to any other position by performing a finite number of rotation on finite number of 2 \times 2 submatrices.

Thus for n>2 we pick the largest $n$ integers after sorting and sum them up.

For n=2 , The answer \max(a_{1,1} + a_{2,2} , a_{1,2} + a_{2,1}).

Complexity \mathcal{O}(n^2 \log n).

def solve():
    n=int(input())
    if(n==2):
        a,b=map(int,input().split())
        c,d=map(int,input().split())
        print(max(a+d,c+b))
    else:
        b=[]
        for i in range(n):
            a=list(map(int,input().split()))
            for j in a:b.append(j)
        b.sort(reverse=1)
        ans=0
        for i in range(n):
            ans+=b[i]
        print(ans)

for _ in range(int(input())):
    solve()