比赛 20131207 评测结果 AAAAAATATTTTW
题目名称 不设找零 最终得分 53
用户昵称 digital-T 运行时间 5.253 s
代码语言 C++ 内存使用 0.67 MiB
提交时间 2013-12-07 16:58:51
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int N,K,coin[17],sum[100001],Ans=-1;
int plan[17];
bool boo[17];
int do_do()
{
	/*for(int i=1;i<=K;i++)
		printf("%d ",coin[plan[i]]);
	printf("\n");*/
	int pre=0,temp,p1,p2,mid;
	for(int i=1;i<=K;i++)
	{
		if(pre==N)
		{
			int ans=0;
			for(int j=i;j<=K;j++)
				ans+=coin[plan[j]];
			//printf("\n");
			return ans;
		}
		p1=pre;
		p2=N;
		while(p2-p1>1)
		{
			if(sum[mid=(p2+p1)/2]-sum[pre]==coin[plan[i]])
				p1=p2=mid;
			else
			{
				if(sum[mid=(p2+p1)/2]-sum[pre]>coin[plan[i]])
					p2=mid;
				else
					p1=mid;
			}
		}
		mid=(p1+p2)/2;
		while(mid<N&&sum[mid+1]-sum[pre]<=coin[plan[i]])
			mid++;
		//printf("%d %d %d\n",mid,pre,sum[mid]-sum[pre]);
		pre=mid;
		//printf("%d ",pre);
	}
	//printf("\n");
	if(pre==K)
		return 0;
	return -1;
}
void dfs(int step,int x)
{
	plan[step]=x;
	boo[x]=1;
	if(step==K)
	{
		Ans=max(Ans,do_do());
		//printf("%d\n",Ans);
		goto NEXT;	
	}
	for(int i=1;i<=K;i++)
		if(!boo[i])
			dfs(step+1,i);
	NEXT:;
	boo[x]=0;
	plan[step]=0;
}
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]);
	int temp;
	sum[0]=0;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&temp);
		sum[i]=sum[i-1]+temp;
	}
	dfs(0,0);
	printf("%d",Ans);
	return 0;
}