Décalage cyclique d'une matrice avec maximisation de la somme de la diagonale

Rust Hard loops

Tâche «Décalage cyclique d'une matrice avec maximisation de la somme de la diagonale»

Soit une matrice carrée d'entiers de taille N x N. En un coup, on peut décaler cycliquement n'importe quelle ligne vers la gauche ou la droite d'un nombre arbitraire de positions, ou décaler cycliquement n'importe quelle colonne vers le haut ou le bas d'un nombre arbitraire de positions. L'objectif est de maximiser la somme des éléments sur la diagonale principale (du coin supérieur gauche au coin inférieur droit). Trouvez la somme maximale possible après un nombre quelconque de ces opérations. N de 1 à 100, les éléments de la matrice sont des entiers de -10^6 à 10^6.

Format d\ entrée

Sur la première ligne, un entier N. Ensuite, N lignes, chacune contenant N entiers séparés par des espaces.

Format de sortie

Un seul entier — la somme maximale sur la diagonale principale.

Exemples

Exemple 1

ENTRÉE

5
1 -2 3 -1 2

SORTIE

5

Exemple 2

ENTRÉE

SORTIE

18

Exemple 3

ENTRÉE

2
3 4
1 2

SORTIE

6

main.rs