P11341 [KTSC 2023 R1] 地牢

**请勿使用 C++14 (GCC 9) 提交。** 你需要在文件开头加入如下代码： ```cpp #include int max_item_sum(std::vector V); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T1 「[던전](https://assets.ioikorea.kr/ioitst/2023/1/dungeon/dungeon_statement.pdf)」** 哲洙和英姬在游戏中需要穿越一个地牢。地牢是一个 $N \times N$ 的网格。网格的行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $N-1$。位于第 $i$ 行，第 $j$ 列的格子记为 $(i, j)$。 穿越地牢的规则如下： - 哲洙从地牢的左上角出发，移动到右下角。每次移动时，哲洙只能向右或向下移动到相邻的格子。 - 英姬从地牢的右上角出发，移动到左下角。每次移动时，英姬只能向左或向下移动到相邻的格子。 地牢的每个格子里都有一个物品。每个物品的价值可以是正整数、$0$ 或负整数，位于 $(i, j)$ 格子的物品价值为 $V[i][j]$。哲洙和英姬已经知道所有格子中物品的价值。穿越地牢后，哲洙和英姬会收集他们经过的所有格子的物品。如果两人都经过同一个格子，那么这个格子的物品只会被收集一次。 请编写一个程序，计算哲洙和英姬能够收集的物品价值的最大可能总和。 你需要实现以下函数： ```cpp int max_item_sum(std::vector V); ``` - `V`：大小为 $N \times N$ 的二维整数数组。对于所有 $i, j$ $(0 \leq i, j \leq N-1)$，$V[i][j]$ 是地牢中 $(i, j)$ 格子的物品价值。 - 该函数返回哲洙和英姬能够收集的物品价值的最大可能总和。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$V[i][0]\,V[i][1]\,\cdots\,V[i][N-1]$

示例评测程序按以下格式输出： - 第 $1$ 行：函数 `max_item_sum` 返回的值

### 样例 1 解释 考虑 $N=5, V=[[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1]]$ 的情况。 评测程序将调用如下函数： ```cpp max_item_sum([[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1],[-1,-1,1,-1,-1],[-1,-1,-1,-1,-1]]); ``` 下图展示了地牢的情况。每个格子中的值表示该格子的物品价值。  下图左侧的蓝色格子表示哲洙经过的格子，右侧的黄色格子表示英姬经过的格子。哲洙经过的格子中物品的总价值为 $-4$，英姬经过的格子中物品的总价值也是 $-4$，两人都经过的格子中物品的总价值为 $-1$。因此，物品的总价值为 $-9$，这是可能的最大总和。  函数应返回 `-9`。 ### 数据范围 对于所有输入数据，满足： - $2 \leq N \leq 1000$ - 对于所有 $i,j$ $(0 \leq i, j \leq N-1)$，$-10^5 \leq V[i][j] \leq 10^5$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $11$ | $N \leq 5$ | | $2$ | $44$ | $N \leq 300$ | | $3$ | $15$ | 对于所有 $i,j$ $(0 \leq i, j \leq N-1)$，$V[i][j] \geq 0$ | | $4$ | $30$ | 无附加限制 |