#include<bits/stdc++.h> #define int long long using namespace std; const int N = 2e5 + 5; int n, k, x; int a[N]; int s[N]; int dp[2][N]; int now; int ans, as; signed main(){ ios::sync_with_stdio(false); cin >> n >> k >> x; if(x < 0){ x = -x; k = n - k; } if(x == 0){ for(int i = 1; i <= n; ++ i){ cin >> a[i]; dp[0][i] = max(0ll, dp[0][i - 1]) + a[i]; ans = max(ans, dp[0][i]); } cout << ans; return 0; } for(int i = 1; i <= n; ++ i){ cin >> a[i]; a[i] -= x; s[i] = s[i - 1] + a[i]; /* if(dp[i - 1] + a[i] >= 0){ dp[i] = dp[i - 1] + a[i]; w[i] = w[i - 1] + 1; } if(dp[i] + min(w[i], k) * (x << 1) > ans){ ans = dp[i] + min(w[i], k) * (x << 1); }*/ } /* for(int i = 1; i <= n; ++ i){ cout << a[i] << ' '; } cout << '\n';*/ for(int i = 1; i <= n; ++ i, now ^= 1){ for(int j = 0; j <= min(i, k); ++ j){ bool f = 0; if(dp[now ^ 1][j] + a[i] >= 0){ dp[now][j] = dp[now ^ 1][j] + a[i]; f = 1; } if(j && dp[now ^ 1][j - 1] + a[i] + (x << 1) >= 0){ if(!f) dp[now][j] = dp[now ^ 1][j - 1] + a[i] + (x << 1); else dp[now][j] = max(dp[now][j], dp[now ^ 1][j - 1] + a[i] + (x << 1)); } if(j == k) ans = max(ans, dp[now][k]); } } cout << ans; return 0; } /* 可先将所有数皆减去 x ，问题变为： 选出一个长度最长为 k 的序列，使得 a[l] + ... a[l + k - 1] + x * min(K, k) 最大 当 k 确定时，可利用单调队列快速求解，目前思路枚举 k 分为 k > K 和 k <= K 的情况 c，莽了个 dp 怎么样例都过了 不过复杂度为 O(nk) ，会炸，就先这样吧 */