D. Maximum path

Codeforces

IDCF762D

Time1000ms

Memory256MB

Difficulty—

dpgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

You are given a rectangular table 3 × _n_. Each cell contains an integer. You can move from one cell to another if they share a side. Find such path from the upper left cell to the bottom right cell of the table that doesn't visit any of the cells twice, and the sum of numbers written in the cells of this path is maximum possible. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 105) — the number of columns in the table. Next three lines contain _n_ integers each — the description of the table. The _j_\-th number in the _i_\-th line corresponds to the cell _a__ij_ ( - 109 ≤ _a__ij_ ≤ 109) of the table. ## Output Output the maximum sum of numbers on a path from the upper left cell to the bottom right cell of the table, that doesn't visit any of the cells twice. [samples] ## Note The path for the first example: <center>![image](https://espresso.codeforces.com/31bfd324f8cc150f7f71fd03ecb141c6eea259e7.png)</center>The path for the second example: <center>![image](https://espresso.codeforces.com/3b50ec31ddbbbb9dba563309087e9653f300cf4b.png)</center>

你被给定一个 3 × n 的矩形表格。每个格子包含一个整数。你可以从一个格子移动到另一个格子，当且仅当它们共享一条边。找到一条从左上角格子到右下角格子的路径，该路径不重复访问任何格子，且路径上格子中数字的和尽可能大。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 表格的列数。接下来三行，每行包含 #cf_span[n] 个整数 —— 表格的描述。第 #cf_span[i] 行的第 #cf_span[j] 个数对应表格中的格子 #cf_span[aij] (#cf_span[ - 109 ≤ aij ≤ 109])。请输出一条从左上角格子到右下角格子、不重复访问任何格子的路径上数字的最大和。第一个例子的路径：第二个例子的路径： ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 表格的列数。接下来三行，每行包含 #cf_span[n] 个整数 —— 表格的描述。第 #cf_span[i] 行的第 #cf_span[j] 个数对应表格中的格子 #cf_span[aij] (#cf_span[ - 109 ≤ aij ≤ 109])。 ## Output 请输出一条从左上角格子到右下角格子、不重复访问任何格子的路径上数字的最大和。 [samples] ## Note 第一个例子的路径：第二个例子的路径：

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10^5 $, be the number of columns. Let $ A = (a_{i,j}) \in \mathbb{Z}^{3 \times n} $ be the grid, where $ a_{i,j} $ is the value in row $ i \in \{1,2,3\} $ and column $ j \in \{1,\dots,n\} $. **Constraints** 1. The path starts at $ (1,1) $ and ends at $ (3,n) $. 2. The path moves only between adjacent cells (sharing a side). 3. No cell is visited more than once. **Objective** Maximize the sum $ \sum_{(i,j) \in P} a_{i,j} $, where $ P $ is a valid path from $ (1,1) $ to $ (3,n) $ satisfying the above constraints.

Samples

Input #1

Output #1

Input #2

5
10 10 10 -1 -1
-1 10 10 10 10
-1 10 10 10 10

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Maximum path",
    "description": {
      "content": "You are given a rectangular table 3 × _n_. Each cell contains an integer. You can move from one cell to another if they share a side. Find such path from the upper left cell to the bottom right cell ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF762D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a rectangular table 3 × _n_. Each cell contains an integer. You can move from one cell to another if they share a side.\n\nFind such path from the upper left cell to the bottom right cell ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个 3 × n 的矩形表格。每个格子包含一个整数。你可以从一个格子移动到另一个格子，当且仅当它们共享一条边。\n\n找到一条从左上角格子到右下角格子的路径，该路径不重复访问任何格子，且路径上格子中数字的和尽可能大。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105]) —— 表格的列数。\n\n接下来三行，每行包含 #cf_span[n] 个整数 —— 表...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^5 $, be the number of columns.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}^{3 \\times n} $ be the grid, where $ a_{i,j} $ is the value in row $ i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments