Zyklische Verschiebung der Matrix mit Maximierung der Diagonalsumme

Rust Hard loops

Aufgabe «Zyklische Verschiebung der Matrix mit Maximierung der Diagonalsumme»

Gegeben ist eine quadratische Matrix aus ganzen Zahlen der Größe N x N. In einem Zug kann man jede Zeile um eine beliebige Anzahl von Positionen zyklisch nach links oder rechts verschieben oder jede Spalte um eine beliebige Anzahl von Positionen zyklisch nach oben oder unten verschieben. Ziel ist es, die Summe der Elemente auf der Hauptdiagonale (von der oberen linken Ecke zur unteren rechten Ecke) zu maximieren. Finden Sie die maximal mögliche Summe nach einer beliebigen Anzahl solcher Operationen. N von 1 bis 100, die Elemente der Matrix sind ganze Zahlen von -10^6 bis 10^6.

Eingabeformat

In der ersten Zeile eine ganze Zahl N. Danach N Zeilen, jede enthält N ganze Zahlen, getrennt durch Leerzeichen.

Ausgabeformat

Eine ganze Zahl – die maximale Summe auf der Hauptdiagonale.

Beispiele

Beispiel 1

EINGABE

5
1 -2 3 -1 2

AUSGABE

5

Beispiel 2

EINGABE

AUSGABE

18

Beispiel 3

EINGABE

2
3 4
1 2

AUSGABE

6

main.rs