WA70求助
查看原帖
WA70求助
556362
Unnamed114514楼主2022/11/27 18:13
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,s,k,dp[1<<16],vis[1<<16],a[20],sum[maxn];
int dfs(int now,int s){
	if(now==n)
		return 0;
	if(vis[s])
		return dp[s];
	int res=1e18;
	for(int i=1;i<=k;++i)
		if(!(s&(1<<i-1))){
			int l=now+1,r=n;
			while(l<r){
				int mid=l+r+1>>1;
				if(sum[mid]-sum[now]<=a[i])
					l=mid;
				else
					r=mid-1;
			}
			if(dfs(r,s|(1<<i-1))!=-1)
				res=min(res,dfs(r,s|(1<<i-1))+a[i]);
		}
	if(res==1e18)
		res=-1;
	vis[s]=1;
	return dp[s]=res;
}
signed main(){
	scanf("%lld%lld",&k,&n);
	for(int i=1;i<=k;++i){
		scanf("%lld",&a[i]);
		s+=a[i];
	}
	for(int i=1;i<=n;++i){
		scanf("%lld",&sum[i]);
		sum[i]+=sum[i-1];
	}
	if(dfs(0,0)==-1)
		puts("-1");
	else
		printf("%lld\n",s-dfs(0,0));
	return 0;
}
2022/11/27 18:13
加载中...