POI Task Termites [A]

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<long long> a(n);
    long long sum = 0;
    int nonZero = 0;
    for (long long &x : a) cin >> x, sum += x, nonZero += !!x;
    vector<vector<long long>> components;
    for (int i = 0; i < n; ++i) {
        if (a[i]) {
            if (!i || !a[i-1]) components.emplace_back();
            components.back().push_back(a[i]);
        }
    }

    for (vector<long long> &c : components) {
        vector<long long> v;
        vector<long long> newbies;
        for (int i = (int)c.size()-1; i >= 0; --i) newbies.push_back(c[i]);
        while (!newbies.empty()) {
            long long X = newbies.back();
            newbies.pop_back();
            v.push_back(X);
            size_t m = v.size();
            if (m >= 3) {
                long long x = v[m-3], M = v[m-2], y = v[m-1];
                if (x <= M && M >= y) {
                    v.resize(m-3);
                    newbies.push_back(x+y-M);
                }
            }
        }
        // now the component will be decreasing and then increasing
        c = v;
    }

    long long difference = 0; // last player's score - other player's score
    if (a.front()) {
        vector<long long> &c = components.front();
        reverse(c.begin(), c.end());
        while (c.size() >= 2) {
            size_t m = c.size();
            long long x = c[m-2], y = c[m-1];
            if (x >= y) break;
            difference += y-x; // for the last player
            c.resize(m-2);
        }
    }
    if (a.back()) {
        vector<long long> &c = components.back();
        while (c.size() >= 2) {
            size_t m = c.size();
            long long x = c[m-2], y = c[m-1];
            if (x >= y) break;
            difference += y-x; // for the last player
            c.resize(m-2);
        }
    }
    vector<long long> values;
    for (const vector<long long> &c : components) values.insert(values.end(), c.begin(), c.end());
    sort(values.begin(), values.end());
    for (size_t i = 0; i < values.size(); ++i) difference += ((i&1) ? -1 : +1) * values[i];

    if (nonZero % 2 == 0) difference = -difference;
    // difference is now first score - second score
    assert((sum+difference)%2 == 0);
    cout << (sum+difference)/2 << ' ' << (sum-difference)/2 << endl;
    return 0;
}