この問題は、C 問題と違いあり得る部分列が \(\binom{N}{M}\) 個あるため、全ての部分列を愚直に試す解法は到底通りそうにありません。

なので、動的計画法を行います。定義は以下の通りです。

・\(\mathrm{dp}[i][j]:=\) \(A_i\) までのうち、すでに \(j\) 個の要素を \(B\) の要素として選んだときの \(\displaystyle \sum_{k=1}^{j} k \times B_k\) の最大値

遷移は、以下のように行われます。

• \(\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]\) は \(A_i\) を \(B\) の要素として選ばなかった場合であり、\(\mathrm{dp}[i-1][j-1]+j \times A_i\) は \(A_i\) を \(B\) の \(j\) 番目の要素として選んだ場合となります。

答えは \(\mathrm{dp}[N][M]\) となります。計算量は \(\mathrm{O}(NM)\) です。

この問題についても、解が 32 bit 型整数の範囲内に収まらないことと解が負になり得ること、\(i > j\) の場合の \(\mathrm{dp}[i][j]\) の扱いに注意してください。

実装例(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;
}