Maksimum İz (Həll təhlili)

Həll

İddia. n>2 matris üçün, matrisi istənilən matrisə yenidən sıralamaq mümkündür.

Tək 2 \times 2 altmatrisi döndərməyi düşünün, onun $4$ fərqli konfiqurasiyasını əldə edə bilərik! Üst-üstə düşən altmatrislərin üstünlüyü ilə, 2 \times 2 altmatrislərdə müəyyən sayda döndürmə apararaq elementləri istənilən digər mövqeyə köçürə bilərik.

Beləliklə, n>2 üçün sıraladıqdan sonra ən böyük $n$ tam ədədini seçir və onların cəmini tapırıq.

n=2 üçün, cavab \max(a_{1,1} + a_{2,2} , a_{1,2} + a_{2,1}).

Komplekslik \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()