Torus Path
Contest: 2022-2023 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules, Preferably Teams)
Difficulty rating: 1500
Tags: greedy, math

You are given a square grid with $$$n$$$ rows and $$$n$$$ columns, where each cell has a non-negative integer written in it. There is a chip initially placed at the top left cell (the cell with coordinates $$$(1, 1)$$$). You need to move the chip to the bottom right cell (the cell with coordinates $$$(n, n)$$$).

In one step, you can move the chip to the neighboring cell, but:

1. you can move only right or down. In other words, if the current cell is $$$(x, y)$$$, you can move either to $$$(x, y + 1)$$$ or to $$$(x + 1, y)$$$. There are two special cases:   if the chip is in the last column (cell $$$(x, n)$$$) and you're moving right, you'll teleport to the first column (to the cell $$$(x, 1)$$$);  if the chip is in the last row (cell $$$(n, y)$$$) and you're moving down, you'll teleport to the first row (to the cell $$$(1, y)$$$).
2. you cannot visit the same cell twice. The starting cell is counted visited from the beginning (so you cannot enter it again), and you can't leave the finishing cell once you visit it.

Your total score is counted as the sum of numbers in all cells you have visited. What is the maximum possible score you can achieve?

Input format:
The first line contains the single integer $$$n$$$ ($$$2 \le n \le 200$$$) — the number of rows and columns in the grid.

Next $$$n$$$ lines contains the description of each row of the grid. The $$$i$$$-th line contains $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, n}$$$ ($$$0 \le a_{i, j} \le 10^9$$$) where $$$a_{i, j}$$$ is the number written in the cell $$$(i, j)$$$.

Output format:
Print one integer — the maximum possible score you can achieve.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
2
1 2
3 4

Example output:
8

Example input:
3
10 10 10
10 0 10
10 10 10

Example output:
80

Editorial:
Note that you can't visit all vertices on the antidiagonal (vertices $$$(1, n), (2, n - 1), \dots (n, 1)$$$) at the same time.
Let's prove it: since you are starting outside the antidiagonal then the only way to visit vertex $$$(x, n + 1 - x)$$$ is to move from $$$(x - 1, n + 1 - x)$$$ or from $$$(x, n - x)$$$. In total, there are $$$n$$$ vertices you can move from — it's vertices $$$(1, n - 1), (2, n - 2), \dots, (n - 1, 1)$$$ and $$$(n, n)$$$. But $$$(n, n)$$$ is the finishing vertices you can't leave, so there are only $$$n - 1$$$ positions left. As a result, you can visit at most $$$n - 1$$$ vertices on the antidiagonal.
Now, let's prove that if you've chosen a vertex $$$(x, n + 1 - x)$$$ you decided to skip, you can always visit all other vertices. Let's use the following simple strategy: let's move right until we meet the restricted or already visited vertex, then move down once then continue moving right and so on.
For example, let's visit all vertices of $$$4 \times 4$$$ matrix except vertex $$$(2, 3)$$$. The path would be the following: $$$(1, 1)$$$ $$$-$$$ $$$(1, 2)$$$ $$$-$$$ $$$(1, 3)$$$ $$$-$$$ $$$(1, 4)$$$ $$$-$$$ $$$(2, 4)$$$ $$$-$$$ $$$(2, 1)$$$ $$$-$$$ $$$(2, 2)$$$ $$$-$$$ $$$(3, 2)$$$ $$$-$$$ $$$(3, 3)$$$ $$$-$$$ $$$(3, 4)$$$ $$$-$$$ $$$(3, 1)$$$ $$$-$$$ $$$(4, 1)$$$ $$$-$$$ $$$(4, 2)$$$ $$$-$$$ $$$(4, 3)$$$ $$$-$$$ $$$(4, 4)$$$.
As a result, the answer is the sum of all elements minus the minimum among $$$a[x][n + 1 - x]$$$, or $$$\sum_{i = 1}^{n}\sum_{j = 1}^{n}a[i][j] - \min_{1 \le x \le n}(a[x][n + 1 - x])$$$.