← 返回题目列表

AtCoder · arc116_f

F. 双端队列游戏

中文机器翻译题面 查看原题

分数: 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