922E - Birds - CodeForces Solution

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int M=1e4+5,N=1e3+5;
ll n,W,B,X;
int A[N],sum,c[N];
inline void init(){
	scanf("%I64d%I64d%I64d%I64d",&n,&W,&B,&X);
	for (int i=1;i<=n;i++){
		scanf("%d",&A[i]);
		sum+=A[i];
	}
	for (int i=1;i<=n;i++){
		scanf("%d",&c[i]);
	}
}
ll dp[N][M];
int ans;

void solve(){
	memset(dp,-1,sizeof dp); dp[0][0]=W;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=sum;j++){
			for (int k=0;k<=min(j,A[i]);k++){
				if (dp[i-1][j-k]==-1) continue;
				ll tmp=min(W+(j-k)*B,dp[i-1][j-k]+X)-(ll)c[i]*k;
				if (tmp<0) continue;
				dp[i][j]=max(dp[i][j],min(W+j*B,tmp));
				ans=max(ans,j);
			}
		}
	}
	printf("%d\n",ans);
}

signed main(){
	init();
	solve();
	return 0;
}