2017.netease.brick.cpp

#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;

#define ff(i, n) for (int i = 0, END = (n); i < END; i ++)
#define fff(i, n, m) for (int i = (n), END = (m); i <= END; i ++)
#define dff(i, n, m) for (int i = (n), END = (m); i >= END; i --)
#define travel(e, first) for (int e = first, v = vv[first]; ~e; e = nxt[e], v = vv[e])
#define clr(a, b) memset(a, b, sizeof(a))
typedef long long ll;

int n;
const int N = 5e5, M = 55;
int dp[2][N + 5], goods[M];

void input() {
    ff(i, n) scanf("%d", goods + i);
}

int solve() {
    clr(dp, -1);
    int now = 0, pre = 1;
    dp[now][0] = 0;

    ff(i, n) {
        int siz = goods[i];
        swap(now, pre); clr(dp[now], -1);

        fff(v, 0, N) if (~dp[pre][v]) {
            dp[now][v] = max(dp[now][v], dp[pre][v]);

            if (v + siz <= N) {
                dp[now][v + siz] = max(dp[now][v + siz], dp[pre][v]);
            }

            dp[now][abs(v - siz)] = max(dp[now][abs(v - siz)], dp[pre][v] + min(siz, v));
        }
    }

    return dp[now][0];
}

int main() {
    while (cin >> n) {
        input();
        int ans = solve();
        printf("%d\n", ans == 0 ? -1 : ans);
    }
}