样例未过但 78pts 求调
查看原帖
样例未过但 78pts 求调
781566
liuyuanpei楼主2024/8/28 15:44
# include <iostream>
# include <cmath>
# include <cstring>
# include <string>
# include <algorithm>
# include <stack>
# include <queue>
# include <vector>
# include <set>
# include <map>
using namespace std;
int k,n;
long long ans=-1;
int dp[1000005];
int a[10005],b[1000005]; 
long long sum[1000005];
int erfen(int x,int st) {
	int l=st,r=n;
	while(l<=r) {
		int mid=(l+r)/2;
		if (sum[mid]-sum[st-1]<x) l=mid+1;
		else r=mid-1;
	}
	return r;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio (false);
    cin.tie(NULL);
    cout.tie(NULL);
	cin >>k>>n;
	for (int i=1;i<=k;i++)
		cin >>a[i];
	for (int i=1;i<=n;i++){
		cin >>b[i];	
		sum[i]=sum[i-1]+b[i];
	}
	for (int i=0;i<(1<<k);i++){
		for (int j=1;j<=k;j++){
			if ((i & (1<<(j-1)))!=0) {
				int pos=erfen(a[j],dp[i^(1<<(j-1))]+1); 
				dp[i]=max(dp[i],pos);
			}
		}
	}
	for (int i=0;i<(1<<k);i++){
		if (dp[i]==n){
			long long cnt=0;
			for (int j=0;j<k;j++)
				if ((i & (1<<j))==0) cnt+=a[j+1];
			ans=max(ans,cnt);
		}
	}
	cout <<ans<<endl;
    return 0;
}

2024/8/28 15:44
加载中...