Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.