Contest Duration: - (local time) (100 minutes) Back to Home
Official

## D - Index × A(Not Continuous ver.) Editorial by en_translator

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;
}

posted:
last update: