题目背景

请勿使用 C++14 (GCC 9) 提交。

你需要在文件开头加入如下代码：

#include<vector>
int max_item_sum(std::vector<std::vector<int>> V);

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1 「던전」

哲洙和英姬在游戏中需要穿越一个地牢。地牢是一个 $N \times N$ 的网格。网格的行从上到下编号为 $0$ 到 $N-1$，列从左到右编号为 $0$ 到 $N-1$。位于第 $i$ 行，第 $j$ 列的格子记为 $(i, j)$。

穿越地牢的规则如下：

• 哲洙从地牢的左上角出发，移动到右下角。每次移动时，哲洙只能向右或向下移动到相邻的格子。
• 英姬从地牢的右上角出发，移动到左下角。每次移动时，英姬只能向左或向下移动到相邻的格子。

地牢的每个格子里都有一个物品。每个物品的价值可以是正整数、$0$ 或负整数，位于 $(i, j)$ 格子的物品价值为 $V[i][j]$。哲洙和英姬已经知道所有格子中物品的价值。穿越地牢后，哲洙和英姬会收集他们经过的所有格子的物品。如果两人都经过同一个格子，那么这个格子的物品只会被收集一次。

请编写一个程序，计算哲洙和英姬能够收集的物品价值的最大可能总和。

你需要实现以下函数：

int max_item_sum(std::vector<std::vector<int>> 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 返回的值

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

-9

5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

60

5
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

15

提示

样例 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]]$ 的情况。

评测程序将调用如下函数：

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$	无附加限制