Максимальний слід (Розбір)

Рішення

Твердження. Для матриці з n>2 можливо перетворити матрицю в будь-яку іншу матрицю.

Розглянемо обертання однієї підматриці 2 \times 2, ми можемо отримати всі $4$ різні конфігурації! Завдяки перекриттю підматриць ми можемо перемістити елементи в будь-яку іншу позицію, виконуючи скінченну кількість обертів на скінченній кількості підматриць 2 \times 2.

Отже, для n>2 ми вибираємо найбільші $n$ цілі числа після сортування та підсумовуємо їх.

Для n=2, відповідь \max(a_{1,1} + a_{2,2} , a_{1,2} + a_{2,1}).

Складність \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()