DGOLD - Chia vàng
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ii pair<int,int>
const int N = 25;
using namespace std;
pair<int, int> f[555555];
int a[N], n, lim, d, res;
int BS(int key) {
int l = 1, r = d, k, m;
while (l<=r) {
m = (l+r) >> 1;
if (f[m].first <= key) {
k = m; l = m+1;
}
else r = m-1;
}
return k;
}
void Gen(int i, int x, int y) {
if (i>lim) {
d++;
f[d].first = x-y;
f[d].second = x;
return;
}
Gen(i+1, x, y);
Gen(i+1, x+a[i], y);
Gen(i+1, x, y+a[i]);
}
void Back(int i, int x, int y) {
if (i>n) {
int t = BS(y-x);
if (f[t].first==(y-x))
res = max(res, f[t].second+x);
return;
}
Back(i+1, x, y);
Back(i+1, x+a[i], y);
Back(i+1, x, y+a[i]);
}
int main()
{
//freopen("DGOLD.in1","r",stdin);
scanf("%d\n", &n);
for(int i=1;i<=n;i++) scanf("%d\n", &a[i]);
lim = n/2;
Gen(1,0,0);
sort(f+1, f+d+1);
Back(lim+1,0,0);
printf("%d", res);
return 0;
}