1765K.md (1870B)
1 Source: https://codeforces.com/problemset/problem/1765/K 2 3 K. Torus Path 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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)$). 22 23 In one step, you can move the chip to the neighboring cell, but: 24 25 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: 26 * 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)$); 27 * 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)$). 28 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. 29 30 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? 31 32 Input 33 34 The first line contains the single integer $n$ ($2 \le n \le 200$) — the number of rows and columns in the grid. 35 36 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)$. 37 38 Output 39 40 Print one integer — the maximum possible score you can achieve. 41 42 Examples 43 44 Input 45 46 ``` 47 2 48 1 2 49 3 4 50 ``` 51 52 Output 53 54 ``` 55 8 56 ``` 57 58 Input 59 60 ``` 61 3 62 10 10 10 63 10 0 10 64 10 10 10 65 ``` 66 67 Output 68 69 ``` 70 80 71 ```