POJ 3977 Subset

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
#define pii pair<ll,int>
#define ll long long
const int MAXN=35;
const int MAXTOT=300000;
int n;
ll a[MAXN+10];
pii res1[MAXTOT+10],res2[MAXTOT+10];
int tot1,tot2;
int cnt;ll sum;
ll myabs(ll a){return (a<0)?(-a):a;}
void solve(int k,int n,pii* res,int& tot)
{
	if(k>n){if(cnt)res[++tot]=make_pair(sum,cnt);return;}
	solve(k+1,n,res,tot);
	++cnt;sum+=a[k];
	solve(k+1,n,res,tot);
	--cnt;sum-=a[k];
}
pii tmp[MAXTOT+10];
void doit(pii* res,int& tot)
{
	int now=1;
	for(int i=2;i<=tot;++i)
	{
		if(res[i].first!=res[i-1].first)tmp[++now]=res[i];
	}
	tot=now;
	for(int i=2;i<=tot;++i)res[i]=tmp[i];
}
void cmp(ll& ans,int& cnt,ll res,int t)
{
	res=myabs(res);
	if(ans==res)cnt=min(cnt,t);
	else if(ans>res)
	{
		ans=res;
		cnt=t;
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	while(scanf("%d",&n),n)
	{
		for(int i=1;i<=n;++i)scanf("%lld",a+i);
		if(n==1){printf("%lld 1\n",myabs(a[1]));continue;}
		int mid=(n>>1);
		cnt=sum=tot1=tot2=0;
		solve(1,mid,res1,tot1);
		solve(mid+1,n,res2,tot2);
		sort(res1+1,res1+tot1+1);
		sort(res2+1,res2+tot2+1);
		doit(res1,tot1);
		doit(res2,tot2);
		ll ans=1e18;int cnt;
		for(int i=1;i<=tot1;++i)
		{
			int left=1,mid,right=tot2,res=1;
			while(left<=right)
			{
				mid=(left+right)>>1;
				if(res2[mid].first<=-res1[i].first)
				{
					res=mid;
					left=mid+1;
				}
				else right=mid-1;
			}
			cmp(ans,cnt,res2[res].first+res1[i].first,res2[res].second+res1[i].second);
			if(res<tot2)cmp(ans,cnt,res2[res+1].first+res1[i].first,res2[res+1].second+res1[i].second);
		}
		for(int i=1;i<=tot1;++i)cmp(ans,cnt,res1[i].first,res1[i].second);
		for(int i=1;i<=tot2;++i)cmp(ans,cnt,res2[i].first,res2[i].second);
		printf("%lld %d\n",myabs(ans),cnt);
	}
	return 0;
}