codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```