DGOLD - Chia vàng
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
int n, a[24], p[13], ans;
pair <int,int> d[1000000], e[1000000];
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
p[0] = 1;
for (int i = 1; i <= 12; i++) p[i] = p[i - 1] * 3;
int n1 = n / 2, n2 = n - n1;
for (int i = 0; i < p[n1]; i++)
{
int s1 = 0, s2 = 0, tmp = i;
for (int j = 0; j < n1; j++)
{
if (tmp % 3 == 1) s1 += a[j];
if (tmp % 3 == 2) s2 += a[j];
tmp /= 3;
}
d[i] = make_pair(s1 - s2, - s1 - s2);
}
for (int i = 0; i < p[n2]; i++)
{
int s1 = 0, s2 = 0, tmp = i;
for (int j = 0; j < n2; j++)
{
if (tmp % 3 == 1) s1 += a[n1 + j];
if (tmp % 3 == 2) s2 += a[n1 + j];
tmp /= 3;
}
e[i] = make_pair(s1 - s2, - s1 - s2);
}
sort(d, d + p[n1]);
int m1 = 1;
for (int i = 1; i < p[n1]; i++)
if (d[i].first != d[m1 - 1].first)
d[m1++] = d[i];
sort(e, e + p[n2]);
int m2 = 1;
for (int i = 1; i < p[n2]; i++)
if (e[i].first != e[m2 - 1].first)
e[m2++] = e[i];
for (int i = 0, j = 0; i < m1 && j < m2;)
{
if (d[i].first == e[j].first) ans = max(ans, - d[i++].second - e[j++].second);
else
if (d[i].first < e[j].first) i++;
else j++;
}
cout << ans / 2 << endl;
}