Seletiva IOI 2017

cabo.cpp

// Ivan Carvalho
// Cabo- Seletiva IOI - OBI 2017
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 27;
const int ADD = 1251;
const int INF = 10000;
vector<int> v1,v2,temp1[MAXN],temp2[MAXN];
int existe1[MAXN][ADD*2],existe2[MAXN][ADD*2];
int passou1[MAXN][ADD*2][MAXN],passou2[MAXN][2*ADD][MAXN];
int NT,M,N,best;
void brute1(int pos,int tot,int qtd){
	if(pos == N){
		if(!existe1[qtd][tot+ADD]){
			temp1[qtd].push_back(tot);
			existe1[qtd][tot + ADD] = 1;
		}
		return;
	}
	if(passou1[pos][tot + ADD][qtd]) return;
	passou1[pos][tot + ADD][qtd] = 1;
	brute1(pos + 1,tot + v1[pos],qtd + 1);
	brute1(pos + 1,tot - v1[pos],qtd);
}
void brute2(int pos,int tot,int qtd){
	if(pos == M){
		if(!existe2[qtd][tot+ADD]){
			temp2[qtd].push_back(tot);
			existe2[qtd][tot + ADD] = 1;
		}
		return;
	}
	if(passou2[pos][tot + ADD][qtd]) return;
	passou2[pos][tot+ADD][qtd] = 1;
	brute2(pos + 1,tot + v2[pos],qtd + 1);
	brute2(pos + 1,tot - v2[pos],qtd);
}
int main(){
	cin >> NT;
	N = NT/2;
	M = NT - N;
	for(int i = 0;i<N;i++){
		int x;
		cin >> x;
		v1.push_back(x);
	}
	for(int i = 0;i<M;i++){
		int x;
		cin >> x;
		v2.push_back(x);
	}
	brute1(0,0,0);
	brute2(0,0,0);
	best = 1e5;
	for(int caras = 0;caras<=N;caras++){
		int outro = N - caras;
		sort(temp1[caras].begin(),temp1[caras].end());
		sort(temp2[outro].begin(),temp2[outro].end());
		int tam = temp2[outro].size();
		for(int diferenca1 : temp1[caras]){
				int oposto = -diferenca1;
				int pos = lower_bound(temp2[outro].begin(),temp2[outro].end(),oposto) - temp2[outro].begin();
				if(pos >= 0 && pos < tam){
					best = min(best, abs(diferenca1 + temp2[outro][pos]) );
				}
				pos--;
				if(pos >= 0 && pos < tam){
					best = min(best, abs(diferenca1 + temp2[outro][pos]) );
				}
				pos += 2;
				if(pos >= 0 && pos < tam){
					best = min(best, abs(diferenca1 + temp2[outro][pos]) );
				}
		}
	}
	cout << best << endl;
	return 0;
}