记录编号	84622	评测结果	AAAAAAAAAAAAA
题目名称	1455.[USACO Nov13] 不设找零	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.284 s
提交时间	2013-12-17 12:08:35	内存使用	0.92 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int A,N,K,coin[17],sum[100001],Ans=-1;
int plan[17];
bool boo[17];
int f[65536];
int main()
{
	freopen("nochange.in","r",stdin);
	freopen("nochange.out","w",stdout);
	scanf("%d%d",&K,&N);
	for(int i=1;i<=K;i++)
	{
		scanf("%d",&coin[i]);
		A+=coin[i];
	}
	int temp;
	sum[0]=0;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&temp);
		sum[i]=sum[i-1]+temp;
	}
	int DDD,p1,p2,mid,pre,k,kk,tmp;
	f[0]=0;
	pre=0;
	DDD=(1<<K)-1;
	for(temp=1,k=1;k<=K;temp<<=1,k++)
	{
		p1=pre;
		p2=N;
		while(p2-p1>1)
		{
			if(sum[mid=(p2+p1)/2]-sum[pre]==coin[k])
				p1=p2=mid;
			else
			{
				if(sum[mid=(p2+p1)/2]-sum[pre]>coin[k])
					p2=mid;
				else
					p1=mid;
			}
		}
		mid=(p1+p2)/2;
		f[temp]=mid;
		//printf("%d\n",mid);
		if(mid==N)
			Ans=max(Ans,A-coin[k]);
	}
	for(int i=1;i<=DDD;i++)
	{
		for(temp=1,k=1;k<=K && temp<=i;temp<<=1,k++)
			if(i & temp)
			{
				pre=f[i-temp];
				p1=pre;
				p2=N;
				while(p2-p1>1)
				{
					if(sum[mid=(p2+p1)/2]-sum[pre]==coin[k])
						p1=p2=mid;
					else
					{
						if(sum[mid=(p2+p1)/2]-sum[pre]>coin[k])
							p2=mid;
						else
							p1=mid;
					}
				}
				mid=(p1+p2)/2;
				if(mid<N&&sum[mid+1]-sum[pre]<=coin[k])mid++;
				f[i]=max(f[i],mid);
				//printf("%d\n",mid);
				if(f[i]==N)
				{
					A=0;
					for(kk=1,tmp=1;kk<=K;kk++,tmp<<=1)
					if((i&tmp)==0)
						A+=coin[kk];
					//printf("%d\n",A);
					Ans=max(Ans,A);
				}
			}
	}
	//printf("%d\n",f[6]);
	printf("%d",Ans);
	return 0;
}