CF1796D Maximum Subarray 题解

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define eb emplace_back
#define int long long
using namespace std;
const int N = 200100;
int f[N][22][2], a[N];
signed main() {
    int T;
    cin >> T;
    while (T--) {
        int n, k, x;
        cin >> n >> k >> x;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            a[i] -= x;
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= min(i, k); ++j) {
                f[i][j][0] = f[i][j][1] = 0;
            }
        }
        x <<= 1;
        int mx = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= min(i, k); ++j) {
                if (i != j) {
                    f[i][j][0] = max({a[i], f[i - 1][j][0] + a[i], f[i - 1][j][1] + a[i]});
                }
                if (j) {
                    f[i][j][1] = max({a[i] + x, f[i - 1][j - 1][0] + a[i] + x, f[i - 1][j - 1][1] + a[i] + x});
                }
                if (k - j <= n - i) {
                    mx = max({mx, f[i][j][0], f[i][j][1]});
                }
            }
        }
        cout << mx << '\n';
    }
    return 0;
}

/*



*/