比赛 20131207 评测结果 AAAAAAWAWWWAW
题目名称 不设找零 最终得分 61
用户昵称 Chenyao2333 运行时间 0.059 s
代码语言 C++ 内存使用 0.67 MiB
提交时间 2013-12-07 17:54:28
显示代码纯文本
#include<stdio.h>

const int MAXN=100000+10;
const int MAXK=16+2;

int K,N;
int S[MAXN]={0};
int val[MAXK]={0};
int ans=0;
int have_m=0;

inline int max(int a,int 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 int sum(int star,int end){
	return S[end]-S[star-1];
}

int get_cost(int s){
	int cost=0;
	for(int i=K;i>0;i--){
		if(s%2)cost+=val[i];
		s/=2;
	}
	return cost;
}

int find(int cost,int w){
		int r=w,l=N;
		while(r<l){
			int m=(r+l)/2;
			if(sum(w,m)<=cost)r=m+1;
			else l=m;
		}
		if(sum(w,r)>cost)r--;
		return r;
}

int is_s[1024]={0};
int solve(int s){
	if(is_s[s])return is_s[s];
	if(s==0)return 1;
	int 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;
		}
		int 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=ret?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;
}