P8102 Cow Insertion Solution

#include <cstdio>
#include <vector>
#include <deque>

// monotony_queue 即 单调队列
std::deque<std::pair<int, int> > dq;
int push_back(int id, int x, int m) {
    while (!dq.empty() && dq.back().second <= x) dq.pop_back();
    dq.push_back({id, x});
    while (!dq.empty() && dq.front().first <= id - m) dq.pop_front();
    return dq.front().second;
}
std::vector<int> monotony_queue(std::vector<int> v, int m) {
    // init
    dq.clear();
    std::vector<int> ans;

    // main
    for (int i = 0; i < m - 1; i++) push_back(i, v[i], m);
    for (int i = m - 1; i < v.size(); i++) {
        ans.push_back(push_back(i, v[i], m));
    }
    return ans;
}

#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int main() {
    static std::vector<int> v, s, u;
    int n, m, A, x;

    // input
    scanf("%d%d%d", &n, &m, &A);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        v.push_back(x);
    }

    // init s, u
    s = monotony_queue(v, m);
    u = monotony_queue(v, m - 1);

    u[0] = max(u[0], A);
    for (int i = 1; i < u.size(); i++) {
        u[i] = max(u[i], A);
        u[i] += u[i - 1];
    }
    u.insert(u.begin(), 0);

    for (int i = 1; i < s.size(); i++) {
        s[i] += s[i - 1];
    }
    s.insert(s.begin(), 0);

    int maxn = -998244353; // ans''
    for (int k = 1; k <= n; k++) { // 这里记得算全 k，否则会 WA
        int l = max(0, k - m + 1);
        int r = min(n - m + 1, k);
        maxn = max(maxn, u[r + 1] - u[l] - s[r] + s[l]);
    }
    maxn += *s.rbegin(); // Don't forget add ans
    printf("%d\n", maxn); // ans'
    return 0;
}