很强的博弈 + 性质题。下文令 A 为 Takahashi，B 为 Aoki。
发现单独考虑一个序列 \(a_1,a_2,...,a_n\)：
- 若 \(n \bmod 2 = 0\)：
- 若 A 为先手，答案为 \(\max(a_{\frac{n}{2}}, a_{\frac{n}{2} + 1})\)；
- 若 B 为先手，答案为 \(\min(a_{\frac{n}{2}}, a_{\frac{n}{2} + 1})\)（由于 \(\min\) 和 \(\max\) 的对称性）。
- 双方都是成为先手比成为后手优。
- 若 \(n \bmod 2 = 1\)：
- 若 A 为先手，答案为 \(\min(a_{\frac{n+1}{2}}, \max(a_{\frac{n+1}{2} - 1}, a_{\frac{n+1}{2} + 1}))\)；
- 若 B 为先手，答案为 \(\max(a_{\frac{n+1}{2}}, \min(a_{\frac{n+1}{2} - 1}, a_{\frac{n+1}{2} + 1}))\)；
- 双方都是成为后手比成为先手优。
相同的结论在 CF794E 也出现过。这是容易归纳证明的，故证明略。
考虑如果全部序列长度都为奇数，容易发现若先手取了其中一个序列的一个数，后手肯定再把这个序列的长度取回奇数。这是因为如果出现了长度为偶数的序列，那它肯定会成为先后手争夺的对象（双方都是成为先手比成为后手优）。所以全部序列的答案可以独立计算再加起来。
现在有一些序列长度为偶数，根据前面的讨论，它们会成为双方争夺的对象。取完偶数的序列后，就回到了上面的情况，并且先后手可能会交换顺序。设 \(x,y\) 为对于一个偶长序列，取头部和取尾部得到的剩下的序列的答案，设 \(mx = \max(x,y), mn = \min(x,y)\)，发现肯定是按 \(mx - mn\) 从大到小先手交替地取。因为如果是 A 取了它，它会比 B 取它多了 \(mx - mn\) 的得分，反之如果 B 取了它，它会比 A 取它少 \(mx - mn\) 的得分。
这样最后的答案由两部分组成，一部分是奇长序列的答案，由于可以单独考虑，所以可以提前确定；另一部分是偶长序列的答案，需要先后手交替取完后转化为奇长序列再记入答案。
时间复杂度线性对数，瓶颈在于排序。
code
// Problem: F - Deque Game
// Contest: AtCoder - AtCoder Regular Contest 116
// URL: https://atcoder.jp/contests/arc116/tasks/arc116_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n;
vector<ll> vc[maxn];
inline bool cmp(pii a, pii b) {
return a.fst - a.scd > b.fst - b.scd;
}
inline ll calc(vector<ll> &a, int op) {
ll m = (ll)a.size();
if (!m) {
return 0;
} else if (m == 1) {
return a[0];
}
if (op) {
if (m & 1) {
return min(a[m / 2], max(a[m / 2 - 1], a[m / 2 + 1]));
} else {
return max(a[m / 2], a[m / 2 - 1]);
}
} else {
if (m & 1) {
return max(a[m / 2], min(a[m / 2 - 1], a[m / 2 + 1]));
} else {
return min(a[m / 2], a[m / 2 - 1]);
}
}
}
void solve() {
scanf("%lld", &n);
int c = 0;
for (int i = 1, k, x; i <= n; ++i) {
scanf("%d", &k);
while (k--) {
scanf("%d", &x);
vc[i].pb(x);
}
c += (vc[i].size() % 2 == 0);
}
vector<pii> S;
ll ans = 0;
if (c & 1) {
for (int i = 1; i <= n; ++i) {
if (vc[i].size() & 1) {
ans += calc(vc[i], 0);
continue;
}
auto a = vc[i], b = vc[i];
a.erase(a.begin());
b.pop_back();
ll x = calc(a, 0), y = calc(b, 0);
S.pb(max(x, y), min(x, y));
}
} else {
for (int i = 1; i <= n; ++i) {
if (vc[i].size() & 1) {
ans += calc(vc[i], 1);
continue;
}
auto a = vc[i], b = vc[i];
a.erase(a.begin());
b.pop_back();
ll x = calc(a, 1), y = calc(b, 1);
S.pb(max(x, y), min(x, y));
}
}
sort(S.begin(), S.end(), cmp);
for (int i = 0, o = 1; i < (int)S.size(); ++i, o ^= 1) {
ans += (o ? S[i].fst : S[i].scd);
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}