记录编号	128334	评测结果	AAAAAAAAAAAAAAAAAAAAA
题目名称	[USACO Open12] 平衡奶牛子集	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.233 s
提交时间	2014-10-17 09:20:08	内存使用	1.77 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=25;
typedef pair<int,int> PR;//first是值,second是二进制码
int N,n;
int a[SIZEN]={0};
int tot=0;
PR state[60000];
bool able[1<<20]={0};
void unique(void){
	sort(state,state+tot);
	int k=0;
	for(int i=0;i<tot;i++)
		if(i==0||state[i]!=state[i-1]) state[k++]=state[i];
	tot=k;
}
void check(PR s){
	int x=-s.first;
	int l=0,r=tot;
	while(l<r){//我们找到第一个>=x的位置
		int mid=(l+r)/2;
		if(state[mid].first>=x) r=mid;
		else l=mid+1;
	}
	while(l<tot&&state[l].first==x){
		able[state[l].second|s.second]=true;
		l++;
	}
}
void DFS2(int p,PR s){
	if(p==N){
		check(s);
		return;
	}
	for(int i=-1;i<=1;i++){
		PR t=s;
		t.first+=i*a[p];
		if(i) t.second|=(1<<p);
		DFS2(p+1,t);
	}
}
void DFS1(int p,PR s){
	if(p==n){
		state[tot++]=s;
		return;
	}
	for(int i=-1;i<=1;i++){
		PR t=s;
		t.first+=i*a[p];
		if(i) t.second|=(1<<p);
		DFS1(p+1,t);
	}
}
void answer(void){
	int ans=0;
	for(int i=(1<<N)-1;i>0;i--) ans+=able[i];
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&N);
	for(int i=0;i<N;i++) scanf("%d",&a[i]);
	n=N/2;
}
int main(){
	freopen("subsets.in","r",stdin);
	freopen("subsets.out","w",stdout);
	read();
	DFS1(0,make_pair(0,0));
	unique();
	DFS2(n,make_pair(0,0));
	answer();
	return 0;
}