#include <iostream> #include <cstring> #include <cstdio> using namespace std; typedef long long i64; const i64 SIZE = 2e5+5, O2 = 5e3+5; const i64 INF = 0x3f3f3f3f3f3f3f3f; i64 n, k, mni[SIZE]; i64 a[SIZE], pre[SIZE], x; i64 dp[O2][O2]; i64 pc(i64 x) { i64 ret = 0; for (; x; x &= x - 1) ++ret; return ret; } void o1() { i64 v = -INF; for (i64 o = 0; o < (1 << n); ++o) { if (pc(o) == k) { for (i64 j = 1; j <= n; ++j) { if (o & (1 << (j - 1))) { a[j] += 2 * x; } mni[j] = 0; } for (i64 i = 1; i <= n; ++i) { pre[i] = pre[i - 1] + a[i]; if (pre[mni[i - 1]] > pre[i]) { mni[i] = i; } else { mni[i] = mni[i - 1]; } } for (i64 i = 1; i <= n; ++i) { if (pre[i] - pre[mni[i]] > v) { v = pre[i] - pre[mni[i]]; } } for (i64 j = 1; j <= n; ++j) { if (o & (1 << (j - 1))) { a[j] -= 2 * x; } } } } printf("%lld\n",max(0ll, v)); } void o2() { memset(dp, -0x3f, sizeof(dp)); i64 ans = -INF; for (i64 i = 1; i <= n; ++i) { for (i64 j = 1; j <= k; ++j) { dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + a[i] + 2 * x); dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i]); if (i > j) dp[i][j] = max(dp[i][j], a[i]); ans = max(ans, dp[i][j]); } } printf("%lld\n",max(ans, 0ll)); } int main() { #ifdef fio freopen("test.in","r",stdin); #endif cin >> n >> k >> x; for (i64 i = 1; i <= n; ++i) { scanf("%lld",a+i); a[i] -= x; pre[i] = pre[i - 1] + a[i]; } for (i64 i = 1; i <= n; ++i) { if (pre[mni[i - 1]] > pre[i]) { mni[i] = i; } else { mni[i] = mni[i - 1]; } } if (n <= 8) { o1(); return 0; } else if (n <= 5e3) { o2(); return 0; } i64 l = -1, r = -1, v = -INF; for (i64 i = 1; i <= n; ++i) { if (pre[i] - pre[mni[i]] > v) { v = pre[i] - pre[mni[i]]; l = mni[i]; r = i; } else if (pre[i] - pre[mni[i]] == v) { if (i - mni[i] > r - l) { l = mni[i], r = i; } } } if (x >= 0) { if (r - l >= k) { printf("%lld\n",max(0ll, pre[r] - pre[l] + 2ll * x * k)); } else { } } else { if (n - r + l >= k) { printf("%lld\n",max(0ll, pre[r] - pre[l])); } else { } } return 0; }