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;
}

Download