C++14(g++5.4) 解法, 执行用时: 86ms, 内存消耗: 1384K, 提交时间: 2020-05-10 09:33:34

#include<bits/stdc++.h>
#define P pair<int,int>
#define ll long long
using namespace std;
const int MX=1e5+9;
ll sum[MX],c[MX],val;
int dp[MX],k,n;

int erfen(ll val,int l,int r){
    if( l>r )
        return r;
    int mid=(l+r)>>1;
    if( sum[mid]<=val )
        erfen(val,mid+1,r);
    else
        erfen(val,l,mid-1);
}

int main()
{
//    freopen("input.txt","r",stdin);
    scanf("%d %d",&k,&n);
    for( int i=0 ; i<k ; i++ )
        scanf("%lld",&c[i]);
    for( int i=1 ; i<=n ; i++ ){
        scanf("%lld",&val);
        sum[i]=sum[i-1]+val;
    }
    sum[n+1]=0x3f;
    ll ans=-1;
    for( int i=0 ; i<(1<<k) ; i++ ){
        ll s=0;
        for( int j=0 ; j<k ; j++ ){
            if( i&(1<<j) )
                dp[i]=max(dp[i],erfen(sum[dp[i^(1<<j)]]+c[j],dp[i^(1<<j)]+1,n));
            else
               s+=c[j];
        }
        if( dp[i]==n )
            ans=max(ans,s);
    }
    printf("%lld\n",ans);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 42ms, 内存消耗: 7776K, 提交时间: 2023-07-27 21:08:21

#include<bits/stdc++.h>
using namespace std;
int dp[66005]={0},S[100005]={0},pos[20][100005];
int main(){
	int i,j,k,n,l,r,a[20];
	long long s,ans=-1;
	scanf("%d%d",&k,&n);
	for(i=0;i<k;i++)
		scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
		scanf("%d",&j),S[i]=S[i-1]+j;
    for(i=0;i<k;i++){
        for(l=r=n;l>=0;l--){
            while(S[r]-S[l]>a[i])
				r--;
            pos[i][l]=r;
        }
    }
    for(i=0;i<(1<<k);i++){
        for(j=0;j<k;j++){
            if((1<<j)&i)
				continue;
            dp[i|(1<<j)]=max(dp[i|(1<<j)],pos[j][dp[i]]);
        }
        if(dp[i]==n){
            for(s=j=0;j<k;j++)
				if(((1<<j)&i)==0)
					s+=a[j];
            ans=max(ans,s);
        }
    }
    printf("%lld\n",ans);
	return 0;
}

C++(clang++11) 解法, 执行用时: 33ms, 内存消耗: 7288K, 提交时间: 2021-04-07 16:57:26

#include<bits/stdc++.h>
using namespace std;

int DP[66005]={0},S[100005]={0},pos[20][100005];
int main()
{
	int i,j,n,m,l,r,a[20];
	long long s,ans=-1;
	scanf("%d%d",&m,&n);
	for(i=0;i<m;i++)scanf("%d",&a[i]);
	for(i=1;i<=n;i++)scanf("%d",&j),S[i]=S[i-1]+j;
	for(i=0;i<m;i++)
	{
		for(l=r=n;l>=0;l--)
		{
			while(S[r]-S[l]>a[i])r--;
			pos[i][l]=r;
		}
	}
	for(i=0;i<(1<<m);i++)
	{
		for(j=0;j<m;j++)
		{
			if((1<<j)&i)continue;
			DP[i|(1<<j)]=max(DP[i|(1<<j)],pos[j][DP[i]]);
		}
		if(DP[i]==n)
		{
			for(s=j=0;j<m;j++)if(((1<<j)&i)==0)s+=a[j];
			ans=max(ans,s);
		}
	}
	printf("%lld\n",ans);
	return 0;
}