UVa 10032 - Tug of War

#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS 1
#endif

#include <iostream>
#include <vector>

using namespace std;
const long long ONE = 1LL;

int nextInt()
{
    int next;
    scanf("%d", &next);
    return next;
}

int main()
{
    int numCases = nextInt();

    vector<int> weights;
    weights.reserve(450);

    while (numCases--)
    {
        int numPeople = nextInt();
        int weightSum = 0;

        for (int i = 0; i < numPeople; i++)
        {
            int weight = nextInt();
            weights.push_back(weight);
            weightSum += weight;
        }

        int halfSum = weightSum / 2;
        int halfPeople = numPeople / 2;

        vector<long long> dp(halfSum + 1);
        dp[0] = 1;

        for (int i = 0; i < numPeople; i++)
        {
            int weight = weights[i];
            for (int j = halfSum; j >= weight; j--)
                dp[j] |= dp[j - weight] << ONE;
        }

        bool odd = (numPeople % 2);
        bool sub = true;

        while (sub)
        {
            int val = dp[halfSum];
            sub = false;

            if (!(val & (ONE << halfPeople)))
                sub = true;

            if (sub && odd && (val & (ONE << (halfPeople + 1))))
                sub = false;

            if (sub) halfSum--;
            else break;
        }

        printf("%d %d\n", halfSum, weightSum - halfSum);
        weights.clear();

        if (numCases > 0)
            cout << endl;
    }

    // release memory
    weights.shrink_to_fit();

    return 0;
}