Baleshare

#define PROG "baleshare"
#define NDEBUG

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <assert.h>

#include <algorithm>
#include <numeric>
#include <iterator>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <complex>

using namespace std;

#define DMP(_fmt, ...) fprintf(stderr, "[file %s, line %d]:" _fmt, __FILE__, __LINE__, __VA_ARGS__)
#define REP(i, n) for(int i = 0; i < (n); ++i)

typedef list<int>::iterator liit;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef complex<double> pt;

FILE *fin, *fout;

// constants and givens/pseudo-constants
// const int MAXN = 1005;
// int N;
// http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
// ^ should be obvious what this is for
// const int NHASH = 193;
// const int NHASH = 6151;
// const int NHASH = 24593;
// const int NHASH = 393241;
const int INF = 999999999;
const int MAXN = 25, MAXS = 105;
int N;
int S[MAXN];

// variables
// int nfoo, a[MAXN];
int total, minB;
bool dp[MAXN * MAXS][MAXN * MAXS];

void init();
void solve();
void init();
void input();
void output();

void solve() {
    init();

    dp[0][0] = true;
    REP(i, N) {
        for (int w1 = total; w1 >= 0; --w1) {
            for (int w2 = total; max(w1, w2) >= S[i] && w2 >= 0; --w2) {
                if (w1 >= S[i]) {
                    dp[w1][w2] |= dp[w1 - S[i]][w2];
                }
                if (w2 >= S[i]) {
                    dp[w1][w2] |= dp[w1][w2 - S[i]];
                }
            }
        }
    }

    minB = INF;
    REP(w1, total) {
        REP(w2, total) {
            if (dp[w1][w2]) {
                assert(w1 + w2 <= total);
                minB = min(minB, max(w1, max(w2, total - w1 - w2)));
            }
        }
    }
}

void init() {
    sort(S, S+N);
    total = accumulate(S, S+N, 0);
}

void input() {
    // fscanf(fin, "%d", &N);
    // for(int i = 0; i < N; ++i) {
    //   fscanf(fin, "%d", a+i);
    // }
    fscanf(fin, "%d", &N);
    REP(i, N) {
        fscanf(fin, "%d", S+i);
    }
}

void output() {
    // fprintf(fout, "%d\n", nfoo);
    fprintf(fout, "%d\n", minB);
}

int main()
{
    fin = fopen(PROG ".in", "r");
    fout = fopen(PROG ".out", "w");
    assert(fin != NULL);
    assert(fout != NULL);

    input();
    solve();
    output();

    fclose(fin);
    fclose(fout);

    exit(0);
}