{"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 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.\n\n## Input\n\nThe first line contains an integer _n_ (1 ≤ _n_ ≤ 105) — the number of columns in the table.\n\nNext 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.\n\n## Output\n\nOutput 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.\n\n[samples]\n\n## Note\n\nThe path for the first example:\n\nThe path for the second example:\n\n","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] 个整数 —— 表格的描述。第 #cf_span[i] 行的第 #cf_span[j] 个数对应表格中的格子 #cf_span[aij] (#cf_span[ - 109 ≤ aij ≤ 109])。\n\n请输出一条从左上角格子到右下角格子、不重复访问任何格子的路径上数字的最大和。\n\n第一个例子的路径：\n\n第二个例子的路径：\n\n## Input\n\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])。\n\n## Output\n\n请输出一条从左上角格子到右下角格子、不重复访问任何格子的路径上数字的最大和。\n\n[samples]\n\n## Note\n\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 \\in \\{1,2,3\\} $ and column $ j \\in \\{1,\\dots,n\\} $.\n\n**Constraints** \n1. The path starts at $ (1,1) $ and ends at $ (3,n) $. \n2. The path moves only between adjacent cells (sharing a side). \n3. No cell is visited more than once. \n\n**Objective** \nMaximize 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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF762D","tags":["dp","greedy","implementation"],"sample_group":[["3\n1 1 1\n1 -1 1\n1 1 1","7"],["5\n10 10 10 -1 -1\n-1 10 10 10 10\n-1 10 10 10 10","110"]],"created_at":"2026-03-03 11:00:39"}}