分数: 800 点
问题陈述
我们有 K 序列。 的 i第一个序列 A_i 的长度为 N_i.
高桥和青木将使用这些玩游戏。 他们将交替执行以下操作,直到每个序列的长度变为 1:
- 选择长度至少为 2,并删除其第一个或最后一个元素。
高桥先行。高桥想要最大化总和 K 元素保留在最后,而 Aoki 希望将其最小化。
求总和 K 当双方玩家都发挥最佳状态时,最终剩余的元素。
约束
- 输入中的所有值都是整数。
- 1 \leq K \leq 2 \times 10^5
- 1 \leq N_i
- \sum_i N_i \leq 2 \times 10^5
- 1 \leq A_{i, j} \leq 10^9
输入
输入由标准输入按以下格式给出:
K
N_1 A_{1, 1} A_{1, 2} \cdots A_{1, N_1}
N_2 A_{2, 1} A_{2, 2} \cdots A_{2, N_2}
\vdots
N_K A_{K, 1} A_{K, 2} \cdots A_{K, N_K}
输出
打印答案。
示例输入 1
2 3 1 2 3 2 1 10
示例输出 1
12
这是游戏的一种可能的进展:
- Takahashi 删除了第一个元素 A_2。现在我们有 A_1 = \left(1, 2, 3\right), A_2 = \left(10\right).
- Aoki 删除最后一个元素 A_1。现在我们有 A_1 = \left(1, 2\right), A_2 = \left(10\right).
- Takahashi 删除了第一个元素 A_1。现在我们有 A_1 = \left(2\right), A_2 = \left(10\right)。每个序列的长度变为 1,所以游戏结束。
在这种情况下, K 最后剩余的元素是 12。请注意,玩家在这里可能做出了次优的动作。
示例输入 2
8 1 2 2 1 2 3 1 2 1 4 1 1 1 2 5 1 1 2 2 1 6 2 2 2 2 1 1 7 1 2 1 1 2 2 2 8 2 2 2 1 1 1 1 2
示例输出 2
12