#include<bits/stdc++.h> #define int long long using namespace std; const int N=5e3+5; int n,m,k; int a[N],ch[N]; int sum[N],mini[N]; int ansi; void dfs(int now,int mi){ if(n-now+1<mi) return; if(now==n+1){ if(mi!=0) return; for(int i=1;i<=n;i++) ansi=max(ansi,sum[i]-mini[i-1]); // if(maxi-mini==4){ // for(int i=1;i<=n;i++) cout<<sum[i]<<" "; // } return; } if(mi>=1){ sum[now]=sum[now-1]+a[now]+k; mini[now]=min(mini[now-1],sum[now]); dfs(now+1,mi-1); } sum[now]=sum[now-1]+a[now]-k; mini[now]=min(mini[now-1],sum[now]); dfs(now+1,mi); } int dp[2][N]; signed main(){ ios::sync_with_stdio(false); cin>>n>>m>>k; for(int i=1;i<=n;i++){ cin>>a[i]; // ch[i]=a[i]-a[i-1]; } // if(n<=8){ // for(int i=1;i<=n;i++) mini[i]=(int)1e9; // dfs(1,m); // cout<<ansi; // return 0; // } for(int i=1;i<=n;i++) a[i]-=k; int now=0; for(int i=1;i<=n;i++){ dp[now][0]=max(dp[now][0],max(dp[now^1][0]+a[i],a[i])); for(int j=1;j<=min(i,m);j++){ if(dp[now^1][j]>0) dp[now][j]=max(dp[now][j],dp[now^1][j]+a[i]); else dp[now][j]=max(dp[now][j],a[i]); if(dp[now^1][j-1]>0) dp[now][j]=max(dp[now][j],dp[now^1][j-1]+a[i]+k*2); else dp[now][j]=max(dp[now][j],a[i]+k*2); } now^=1; } // for(int i=1;i<=n;i++){ // for(int j=0;j<=m;j++){ // cout<<dp[i][j]<<" "; // } // cout<<"\n"; // } cout<<dp[now^1][m]; return 0; } /* ÎÒ»á20pts×ö·¨/cy£¨´óÎí */ //dp[i][j]±íʾǰi¸öÀïÃæÑ¡ÁËj¸öµÄ×î´óÇø¼äºÍ