吐槽:这题数据太水了吧 | 70分同志可以进来看看
查看原帖
吐槽:这题数据太水了吧 | 70分同志可以进来看看
237541
___balalida___楼主2021/6/6 13:04

RT

#define N 220000
ll n,sum[N],m,a[N],f[1<<18],g[1<<18],tot,ans=998244353123456,b[N];
ll get(ll x,ll pos){
	ll l=pos,r=m;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(sum[mid]-sum[pos-1]==x)return mid;
		if(sum[mid]-sum[pos-1]<x)l=mid+1;
		else r=mid-1;
	}
	return r;
}
int main(){
	n=read(),m=read();rep(i,1,n)a[i]=read(),tot+=a[i];ll S=(1<<n)-1;
	rep(i,1,m)b[i]=read(),sum[i]=sum[i-1]+b[i];
	rep(s,0,S){
		rep(i,0,n-1)if((s>>i)&1){
			ll x=s^(1<<i),tmp=get(a[i+1],f[x]+1);
			if(tmp>f[s])f[s]=tmp,g[s]=g[x]+a[i+1];
			if(f[s]==m)ans=min(ans,g[s]);
		}
	}
	write(tot<ans?-1:tot-ans);
}

ll x=s^(1<<i)改成ll x=s|(1<<i)有70分

以为是细节问题看了别的地方好久

2021/6/6 13:04
加载中...