Type: Default 1000ms 256MiB

Deque Game

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC116F] Deque Game

题面翻译

KK 个数列,第 ii 个数列的长度为 NiN_i,命名为 AiA_i。第 ii 个数列的第 jj 个元素被称为 Ai,jA_{i,j}

Takahashi 和 Aoki 在玩游戏。每一轮中,可以选择一个剩余元素数量 >1>1 的数列,并删掉最前面或者最后面的元素。

Takahashi 先手。当每个数列都只剩下一个元素时,游戏结束。

定义一局游戏的得分为最后剩下的元素之和。Takahashi 想要最大化得分,而 Aoki 想要最小化得分。

假设两人都绝顶聪明,请输出最后的得分。

输入格式

第一行一个整数 KK ,接下来 KK 行,每行第一个整数 NiN_i 表示第 ii 个数列有多少个数,后面 NiN_i 个数表示这个数列。

K K N1 N_1 A1, 1 A_{1,\ 1} A1, 2 A_{1,\ 2} \cdots A1, N1 A_{1,\ N_1} N2 N_2 A2, 1 A_{2,\ 1} A2, 2 A_{2,\ 2} \cdots A2, N2 A_{2,\ N_2} \vdots NK N_K AK, 1 A_{K,\ 1} AK, 2 A_{K,\ 2} \cdots AK, NK A_{K,\ N_K}

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

2
3 1 2 3
2 1 10

样例输出 #1

12

样例 #2

样例输入 #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

提示

数据范围

  • 1  K  2 × 1051\ \leq\ K\ \leq\ 2\ \times\ 10^5
  • 1  Ni1\ \leq\ N_i
  • i Ni  2 × 105\sum_i\ N_i\ \leq\ 2\ \times\ 10^5
  • 1  Ai, j  1091\ \leq\ A_{i,\ j}\ \leq\ 10^9

20241224集训

Not Attended
Status
Done
Rule
IOI
Problem
6
Start at
2024-12-24 19:00
End at
2024-12-24 21:00
Duration
2 hour(s)
Host
Partic.
15