A1791 [USACO24DEC] Cake Game S

#include <bits/stdc++.h>
using namespace std;

// [USACO24DEC] Cake Game S
//
// 结论：Bessie（先手，负责合并相邻蛋糕）在最优博弈下吃到的是
// 「所有长度为 N/2+1 的连续窗口中，和最小的那一个」。
//
// 理由概要：
//   * 一共 N-1 个回合，Bessie 合并 N/2 次、Elsie 藏 N/2-1 次，
//     所以最后 Bessie 吃到的是一段连续的 N/2+1 个蛋糕。
//   * Bessie 的最优策略是「每次合并正中间的两个」，这样 Elsie 每藏一端，
//     最终窗口就往另一侧挪一格，Elsie 能把窗口逼到任意位置；
//     而无论 Bessie 怎么合并，Elsie 都能保证最终窗口的和不超过最小窗口和。
//   （完整证明见 solution.md）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        long long total = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            total += a[i];
        }

        // 长度为 n/2+1 的窗口和，用滑动窗口 O(n) 算出来
        int w = n / 2 + 1;
        long long sum = 0;
        for (int i = 0; i < w; i++) sum += a[i];
        long long bessie = sum;
        for (int i = w; i < n; i++) {
            sum += a[i] - a[i - w];
            bessie = min(bessie, sum);
        }
        long long elsie = total - bessie;

        cout << bessie << " " << elsie << "\n";
    }
    return 0;
}