Unlike problem C, in this problem there are \(\binom{N}{M}\) possible subsequences, so it is far impossible to try all the subsequences naively.

That’s why we use DP (Dynamic Programming). It is defined as follows:

• The maximum value of \(\displaystyle \sum_{k=1}^{j} k \times B_k\) when choosing \(j\) elements for \(B\) from the elements from \(A_1\) to \(A_i\).

The transition goes as follows:

• \(\mathrm{dp}[i][j]=\max(\mathrm{dp}[i-1][j],\mathrm{dp}[i-1][j-1]+j \times A_i)\)

\(\mathrm{dp}[i-1][j]\) corresponds to when \(A_i\) is not chosen as an element of \(B\), and \(\mathrm{dp}[i-1][j-1]+j \times A_i\) to when \(A_i\) is chosen as the \(j\)-th element of \(B\).

The answer is \(\mathrm{dp}[N][M]\). The complexity is \(\mathrm{O}(NM)\).

For this problem also, note that the solution may not fit in 32-bit integer type. Be careful of handling \(\mathrm{dp}[i][j]\) when \(i > j\).

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
long long dp[2001][2001];
int main(){
  int n,m;
  cin>>n>>m;
  vector<long long> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  dp[0][0]=0;
  dp[0][1]=-1000000000000000000ll;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=n;j++){
      if(j==0) dp[i][0]=0;
      else if(j>i) dp[i][j]=-1000000000000000000ll;
      else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a[i-1]*j);
    }
  }
  cout<<dp[n][m]<<endl;
}