求调
查看原帖
求调
936249
zhangqiuyanAFOon2024楼主2024/7/17 17:32
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int dp[1<<17],a[N],m[N],sum[N],id;
int find(int x,int l,int r){
	while(l<r){
		int mid=(l+r)/2;
		if(sum[mid]-sum[id]>=x) l=mid+1;
		else r=mid;
	}
	return l;
}
signed main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=k;i++) cin>>m[i],sum[i]=sum[i-1]+m[i];
	for(int i=0;i<(1<<n);i++){
		for(int j=1;j<=n;j++){
			if((1<<j-1)&i){
				id=dp[i-(1<<j-1)];
				int p=find(a[j],id,k);
				dp[i]=max(dp[i],p);
			} 
		}
	}
	int ans=0,maxn=-1;
	for(int i=0;i<(1<<n);i++){
		int ans=0;
		if(dp[i]==k)
			for(int j=1;j<=n;j++){
				if((1<<j-1)&i) ans+=a[j];
			}
		maxn=max(maxn,sum[n]-ans);
	}
	cout<<maxn;
	return 0;
}
2024/7/17 17:32
加载中...