记录编号	84503	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Nov13] 不设找零	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	0.309 s
提交时间	2013-12-14 15:17:29	内存使用	1.67 MiB

#include<stdio.h>
 
const int MAXN=100000+10;
const int MAXK=16+2;
 
typedef int  LL;
 
int K,N;
LL S[MAXN]={0};
LL val[MAXK]={0};
LL ans=0;
LL have_m=0;
 
inline LL max(LL a,LL b){
	return a>b?a:b;
}
 
void read(){
	//int t;
	scanf("%d %d",&K,&N);
	for(int i=1;i<=K;i++){
		scanf("%d",&val[i]);
		have_m+=val[i];
	}
	for(int i=1;i<=N;i++){
		scanf("%d",&S[i]);
		S[i]+=S[i-1];
	}
}
 
inline LL sum(int star,int end){
	return S[end]-S[star-1];
}
 
LL get_cost(int s){
	LL cost=0;
	for(int i=K;i>0;i--){
		if(s%2)cost+=val[i];
		s/=2;
	}
	return cost;
}
 
int find(LL cost,int w){
	int left=w,right=N;
	while(left<right){
		int m=(left+right)/2;
		if(sum(w,m)<=cost)left=m+1;
		else right=m;
	}
	if(sum(w,right)>cost)right--;
	return right;
}
 
LL is_s[1<<MAXK]={0};
LL solve(int s){
	if(is_s[s])return is_s[s];
	if(s==0)return 1;
	LL ret=0;
	for(int p=1;p<(1<<K);p=p<<1){
		if((s&p)==0)continue;
		int w=solve(s^p);
		if(w>N){
			ret=N+1;
			continue;
		}
		LL cost=get_cost(p);
		int l=find(cost,w);
		if(l>=N){
			ans=max(have_m-get_cost(s),ans);
			ret=N+1;
		}else ret=max(ret,l+1);
	}
	is_s[s]=ret;
	return ret;
}
 
void open(){
	freopen("nochange.in","r",stdin);
	freopen("nochange.out","w",stdout);
}	
 
int main(){
	open();
	read();
	int w=solve((1<<K)-1);
	if(w>N)printf("%d",ans);
	else printf("-1");
	return 0;
}