Solution using 1d Dp


#1
int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
int t = *max_element(A.begin(),A.end());
int dp[t+1];
memset(dp,-1,sizeof(dp));
dp[0] = 0;
int k = 0;
for(auto i:B){
    for(int j = i; j <=t; j++){
        if(dp[j-i]!=-1)
        dp[j] = dp[j]==-1 ? dp[j-i]+C[k] : min(dp[j],dp[j-i]+C[k]);
    }
    k++;
}
int ans = 0;
for(auto i:A) ans+=dp[i];
return ans;
}