Can someone help me in this:
I could only score 20 points.
It is just bitmask dp in O(mn2^m).
vector<ll> dp(1<<m, -1e18);
ll ans = 0;
dp[0] = 0;
for(int i=1;i<=n;i++){
for(int j=(1<<m)-1;j>=0;--j){
dp[j] = dp[j] + a[i-1];
for(int k=0;k<m;k++){
if(j&(1<<k)) dp[j] = max(dp[j], dp[j^(1<<k)] + (b[k]+1)*a[i-1]);
}
}
dp[0] = max(dp[0], a[i-1]);
for(int j=0;j<m;j++){
dp[(1<<j)] = max(dp[(1<<j)], a[i-1]*(b[j] + 1));
}
ans = max(ans,dp[(1<<m)-1]);
}
cout<<ans<<"\n";
btw @munghatekartik
Now randomly select exactly m elements from the subarray
Randomly is not correct here.
Hi,
Can you explain a bit more about your approach and also suggest some problems? What I understood is that dp[mask] denotes the maximum sum using bits set in mask. But how did you form it? Where are the subarrays being considered??
Thanks
dp[i][mask] represents the larges sum of a suffix ending at i, such that we have chosen to multiply some elements with some elements of b. The elements of b we have multiplied with is stored in mask. The first case is when we choose to not multiply a_i, with anything, and the second case we are multiplying it by something.
Finally, we are trying to see the maximum sum if we only consider a_i, and drop the suffix.
We just want max(dp[i](2^m - 1]), since we need to multiply some elements in the subarray with all elements in b.