Với ~n~ lẻ, ~illya~ có thể chọn hết tất cả ~\left\lfloor \frac{n}{2} \right\rfloor~ số ở các vị trí chẵn nếu muốn, vì vậy cách tối ưu nhất là sắp xếp sao cho ~\left\lfloor \frac{n}{2} \right\rfloor~ số lớn nhất của dãy ~a~ nằm ở các vị trí chẵn, số điểm cuối cùng của ~illya~ là tổng ~\left\lfloor \frac{n}{2} \right\rfloor~ số lớn nhất đó.

Cụ thể cách ~illya~ lấy tất cả các số ở vị trí chẵn như sau: nếu lượt ngay trước đó ~nkwn~ chọn số đầu dãy thì ~illya~ cũng chọn số đầu dãy, ngược lại nếu ~nkwn~ chọn số cuối dãy thì ~illya~ cũng chọn số cuối dãy.

Với ~n~ chẵn:

Nhận xét: ~nkwn~ có thể lấy toàn bộ các số ở vị trí chẵn hoặc toàn bộ các số ở vị trí lẻ nếu muốn.

Gọi ~A~ là tập các số ở vị trí lẻ, ~B~ là tập các số ở vị trí chẵn.

Theo nhận xét bên trên, nếu ~nkwn~ chơi tối ưu, số điểm ~nkwn~ đạt được sẽ không nhỏ hơn ~max(sum(A), sum(B))~.

Có thể chứng minh được(*): Nếu ~illya~ cũng chơi tối ưu, số điểm ~nkwn~ đạt được là ~max(sum(A), sum(B))~, và điểm của ~illya~ là ~min(sum(A), sum(B))~.

Do đó, ~illya~ cần tìm cách chia dãy ~a~ ban đầu thành 2 dãy con có số phần tử bằng nhau (tất nhiên không cần liên tiếp) sao cho tổng của dãy có tổng nhỏ hơn là lớn nhất có thể.

Sử dụng kĩ thuật quy hoạch động tương tự bài toán cái túi để giải các subtask đầu, kết hợp kiểu dữ liệu bitset để giải được subtask cuối cùng.

(*): ~illya~ sắp xếp dãy ~a~ sao cho:

• Dãy con chỉ gồm các số ở vị trí lẻ của dãy ~a~ là dãy không giảm.
• Dãy con chỉ gồm các số ở vị trí chẵn của dãy ~a~ là dãy không tăng.

~illya~ thực hiện các lượt chơi theo chiến thuật giống với trường hợp ~n~ lẻ: nếu lượt ngay trước đó ~nkwn~ chọn số đầu dãy thì ~illya~ cũng chọn số đầu dãy, ngược lại nếu ~nkwn~ chọn số cuối dãy thì ~illya~ cũng chọn số cuối dãy.

Theo chiến thuật trên, giả sử có ~x~ lượt trong ~n/2~ lượt ~nkwn~ chọn số đầu dãy, và ~y = n/2 - x~ lượt ~nkwn~ chọn số cuối dãy.

Gọi ~A~ là tập các số ở vị trí lẻ, ~B~ là tập các số ở vị trí chẵn, số điểm ~nkwn~ đạt được ~d~ là tổng ~x~ phần tử nhỏ nhất trong ~A~ và ~y~ phần tử nhỏ nhất trong ~B~.

Có ~2~ trường hợp:

• Nếu tổng ~y~ phần tử lớn nhất trong ~A~ lớn hơn tổng ~y~ phần tử nhỏ nhất trong ~B~, suy ra ~d < sum(A)~.
• Nếu tổng ~y~ phần tử lớn nhất trong ~A~ nhỏ hơn hoặc bằng tổng ~y~ phần tử nhỏ nhất trong ~B~, suy ra tổng ~x~ phần tử nhỏ nhất trong ~A~ nhỏ hơn hoặc bằng tổng ~x~ phần tử lớn nhất trong ~B~, vậy ~d \leq sum(B)~

Vì vậy, trong mọi trường hợp, số điểm của ~nkwn~ không vượt quá ~max(sum(A), sum(B))~.

Lưu ý: ~sum(A)~ là tổng các phần tử của dãy/tập hợp ~A~.

Code mẫu

#include <bits/stdc++.h>

#define fi first
#define se second
#define For(i, a, b) for (int i=a;i<=b;++i)
#define Ford(i, a, b) for(int i=a;i>=b;--i)

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> arr;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 5 * 1e5 + 5;

int a[N];
bitset<N> f[55];

void solve()
{
    int n; cin >> n;
    For(i, 1, n) cin >> a[i];

    sort(a + 1, a + 1 + n);

    int s = 0;
    For(i, 1, n) s += a[i];
    if (n & 1) {
        int x = 0;
        For(i, n / 2 + 2, n) x += a[i];
        cout << x << " " << s - x << "\n";
        return;
    }

    f[0][0] = 1;
    For(i, 1, n) {
        Ford(j, min(i, n / 2), 1) {
            f[j] |= (f[j - 1] << a[i]);
        }
    }

    Ford(i, s / 2, 0) {
        if (f[n / 2][i]) {
            cout << i << " " << s - i;
            return;
        }
    }
}

int main()
{
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    solve();

    return 0;
}