题目

分析

首先 \(n^2\) 很显然是个 \(dp\) ，然后显然是需要从低位到高位考虑，因为这样可以让前面的位不对后面造成影响。（比如NOIP2021T2）

然后考虑设状态 \(dp[i][j]\) 表示现在选了前 \(i\) 位，第 \(i\) 位当前有 \(j\) 个数的最大贡献值。

转移方程就是：

\(1.\) 如果当前这个要选： \(dp[i][j-1] \to dp[i][j]\) 。

\(2.\) 如果要扩展上去一层： \(dp[i][j] \to dp[i+1][\lfloor\frac j2\rfloor]\) 。

注意第二个状态的扩展其复杂度是 \(n+\frac n2 +\frac n4+...=O(n)\) （因为要枚举第二维的只有当前最多可以进位的）

代码

#include
using namespace std;
//#ifdef ONLINE_JUDGE
//	#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//	char buf[1<<21],*p1=buf,*p2=buf;
//#endif
template
inline void read(T &x){
	x=0;bool f=false;char ch=getchar();
	while(!isdigit(ch)){f|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
	x=f?-x:x;
	return ;
}
template
inline void write(T x){
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10^48);
	return ;
}
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define PII pair
#define rep(i,x,y) for(register int i=(x);i<=(y);i++)
#define dep(i,y,x) for(register int i=(y);i>=(x);i--)
#define repg(i,x) for(int i=head[x];i;i=nex[i])
#define filp(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define infilp(s) freopen(s".in","r",stdin)
#define outfilp(s) freopen(s".out","w",stdout)
const int MOD=1e9+7;
inline int inc(int x,int y){x+=y;return x>=MOD?x-MOD:x;}
inline int dec(int x,int y){x-=y;return x<0?x+MOD:x;}
inline void incc(int &x,int y){x+=y;if(x>=MOD) x-=MOD;}
inline void decc(int &x,int y){x-=y;if(x<0) x+=MOD;}
inline void chkmin(int &x,int y){if(yx) x=y;}
const int N=4005,M=2e5+5,INF=1e9+7;
int n,m,c[N],l[N],s[N],Ans;
int dp[N][N],t[N];//dp[i][j]表示前i位已经决定好了，当前这一位有j个数，目前的最大值 
signed main(){
//	double ST=clock();
	// ios::sync_with_stdio(false);
//#ifndef ONLINE_JUDGE
//	filp("my");
//#endif
	read(n),read(m);m+=n;
	dep(i,n,1) read(l[i]);
	dep(i,n,1) read(s[i]);
	rep(i,1,m) read(c[i]);
	memset(dp,-0x3f,sizeof(dp));
	t[0]=n;
	rep(i,1,m) dp[i][0]=0;
	rep(i,1,n) t[i]=t[i-1]>>1;
	rep(i,1,n){
		const int now=l[i];
		dep(j,i,1) chkmax(dp[now][j],dp[now][j-1]+c[now]-s[i]);
		rep(j,now,m) rep(k,0,t[j-now]) chkmax(dp[j+1][k/2],dp[j][k]+k/2*c[j+1]);
	}
	write(dp[m][0]);
//	cerr<<"\nTime:"<<(clock()-ST)/CLOCKS_PER_SEC<<"s\n";
	return 0;
}
/*
*/