DGOLD - Chia vàng
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <map>
#include <vector>
#define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i >= _b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)
using namespace std;
int n, a[25], res;
struct HashTable {
static const int HKEY = 1000003;
vector< pair<int,int> > h[HKEY];
inline int key(int s) const {
int res = s % HKEY;
if (res < 0) res += HKEY;
return res;
}
void insert(int s, int val) {
int k = key(s);
REP(i,h[k].size())
if (h[k][i].first == s) {
h[k][i].second = max(h[k][i].second, val);
return ;
}
h[k].push_back(make_pair(s, val));
}
int get(int s) {
int k = key(s);
REP(i,h[k].size()) {
if (h[k][i].first == s)
return h[k][i].second;
}
return -1000111000;
}
} best;
void attempt1(int i, int r, int sum1, int sum2) {
if (i > r) {
best.insert(sum1 - sum2, sum1);
return ;
}
attempt1(i+1, r, sum1, sum2);
attempt1(i+1, r, sum1+a[i], sum2);
attempt1(i+1, r, sum1, sum2+a[i]);
}
void attempt2(int i, int r, int sum1, int sum2) {
if (i > r) {
res = max(res, best.get(sum2-sum1) + sum1);
return ;
}
attempt2(i+1, r, sum1, sum2);
attempt2(i+1, r, sum1+a[i], sum2);
attempt2(i+1, r, sum1, sum2+a[i]);
}
int main() {
scanf("%d", &n); FOR(i,1,n) scanf("%d", &a[i]);
int l1 = 1, r1 = n/2;
int l2 = r1+1, r2 = n;
attempt1(l1, r1, 0, 0);
attempt2(l2, r2, 0, 0);
cout << res << endl;
}