Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
K 個の数列が与えられます。 i 個目の数列 A_i の長さは N_i です。
これらを使って高橋君と青木君がゲームをします。 全ての数列が長さ 1 になるまで、高橋君と青木君が交互に以下の操作を行います。
- 長さが 2 以上の数列を 1 つ選び、その最初の要素或いは最後の要素を削除する。
高橋君が先に操作を行います。最後に残る K 個の要素の総和を、高橋君は最大化したいと、青木君は最小化したいと考えています。
両者最適に行動するとき、最後に残る 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
ゲームの進行の一例を示します。
- 高橋君が A_2 の最初の要素を削除する。現在の数列の状態は、 A_1 = \left(1, 2, 3\right), A_2 = \left(10\right) である。
- 青木君が A_1 の最後の要素を削除する。現在の数列の状態は、 A_1 = \left(1, 2\right), A_2 = \left(10\right) である。
- 高橋君が 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
Score : 800 points
Problem Statement
We have K sequences. The i-th sequence A_i has the length of N_i.
Takahashi and Aoki will play a game using these. They will alternately do the following operation until the length of every sequence becomes 1:
- Choose a sequence of length at least 2, and delete its first or last element.
Takahashi goes first. Takahashi wants to maximize the sum of the K elements remaining in the end, while Aoki wants to minimize it.
Find the sum of the K elements remaining in the end when both players play optimally.
Constraints
- All values in input are integers.
- 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
Input
Input is given from Standard Input in the following format:
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}
Output
Print the answer.
Sample Input 1
2 3 1 2 3 2 1 10
Sample Output 1
12
Here is one possible progression of the game:
- Takahashi deletes the first element of A_2. Now we have A_1 = \left(1, 2, 3\right), A_2 = \left(10\right).
- Aoki deletes the last element of A_1. Now we have A_1 = \left(1, 2\right), A_2 = \left(10\right).
- Takahashi deletes the first element of A_1. Now we have A_1 = \left(2\right), A_2 = \left(10\right). The length of every sequence has become 1, so the game ends.
In this case, the sum of the K elements remaining in the end is 12. Note that the players may have made suboptimal moves here.
Sample Input 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
Sample Output 2
12