DGOLD - Chia vàng

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<bits/stdc++.h>
using namespace std;

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 24, MAX = 531441;
int a[N], n;
pair<int, int> c1[MAX], c2[MAX];

void backtrack(int l, int r, pair<int, int> res[], int &c, int w1 = 0, int w2 = 0) {
	if(l == r) res[c++] = make_pair(w1 - w2, w1 + w2);
	else {
		backtrack(l+1, r, res, c, w1, w2);
		backtrack(l+1, r, res, c, w1 + a[l], w2);
		backtrack(l+1, r, res, c, w1, w2 + a[l]);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n; for(int i = 0; i < n; ++i) cin >> a[i];
	int n1 = 0, n2 = 0;
	backtrack(0, n/2, c1, n1); backtrack(n/2, n, c2, n2);
	sort(c1, c1+n1); sort(c2, c2+n2);
	int res = 0;
	for(int i = 0, j = n2-1; i < n1; ++i) {
		while(j > 0 && c1[i].first + c2[j].first > 0) --j;
		if(c1[i].first + c2[j].first == 0)
			res = max(res, c1[i].second + c2[j].second);
	}
	cout << res/2 << '\n';
	return 0;
}

Download