记录编号	597594	评测结果	AAAAAAAAAAAAA
题目名称	[USACO Nov13] 不设找零	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.549 s
提交时间	2024-12-04 18:28:07	内存使用	3.83 MiB

#include<bits/stdc++.h>
using namespace std;
long long f[1<<20],a[1000010],n,c[1000010],res=-1,m,sum;
int main(){
		 freopen("nochange.in","r",stdin);
    freopen("nochange.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>c[i];
		sum+=c[i];
	}
	for(int i=1;i<=m;i++){
		cin>>a[i];
		a[i]+=a[i-1];
	}
	f[0]=0;
	for(int i=0;i<=(1<<n)-1;i++){
		if(f[i]==m)
		continue;
		for(int j=1;j<=n;j++){
			if(((1<<(j-1))&i)!=0)
			continue;
			long long l=f[i]+1,r=m,p=a[f[i]],ans=-1;
			while(l<=r){
				int mid=(l+r)/2;
				int s=a[mid]-p;
				if(s<=c[j]){
				    ans=mid;
					l=mid+1;
				}
				else{
					r=mid-1;
				}
			}
			f[i|(1<<(j-1))]=max(f[i|(1<<(j-1))],ans);
		}
	}
	for(int i=0;i<=(1<<n)-1;i++){
		if(f[i]==m){
			int num=0;
			for(int j=1;j<=n;j++){
				if((1<<(j-1)&i)!=0){
					num+=c[j];
				}
			}
			res=max(res,sum-num);
		}
	}
	cout<<res;
	return 0;
}