IOIC '22 p52. 序列分割

#include <cstdio>

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#include <unistd.h>

const int S = 65536;

int OP = 0;
char OB[S];

inline char RC() {
    static char buf[S], *p = buf, *q = buf;
    return p == q and (q = (p = buf) + read(0, buf, S)) == buf ? -1 : *p++;
}

inline int RI() {
    static char c;
    int a;
    while (((c = RC()) < '0' or c > '9') and c != '-' and c != -1);
    if (c == '-') {
        a = 0;
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a -= c ^ '0';
    }
    else {
        a = c ^ '0';
        while ((c = RC()) >= '0' and c <= '9') a *= 10, a += c ^ '0';
    }
    return a;
}

/// Fast I/O by FHVirus ///
/// https://fhvirus.github.io/blog/2020/fhvirus-io/ ///

#define int long long

const int INF = 1E17;

struct Line {
    int a, b, id; /// ax+b
    Line(int _a = 0, int _b = 0, int _id = 0) : a(_a), b(_b), id(_id) {}
    int val(int x) {return a*x + b;}
};

inline bool check(Line l1, Line l2, Line l3, int x) {
    return (((l3.a - l2.a) * (l1.b - l2.b) >= (l3.b - l2.b) * (l1.a - l2.a))
        and (l2.b - l3.b < x * (l3.a - l2.a)));
}

signed main() {
    /// dp[i] = a[i] + b*i*i + max(dp[j] + b*j*j + 2*b*j*i) ///
    /// dp[0] = a[0] ///
    /// transfer from j which max(i-K, 0) <= j < i ///

    int N = RI(), K = RI(), B = RI();

    int A[N];
    for (int &x : A) x = RI();

    int dp[N];
    for (int i = 1; i < N; ++i) dp[i] = -INF;
    dp[0] = A[0];

    int fr = 0, bk = 0;
    Line deq[N];
    deq[bk++] = Line(0, dp[0], 0);
    for (int i = 1; i < N; ++i) {
        if (deq[fr].id < i-K) ++fr;
        while (bk - fr >= 2 and deq[fr].val(i) < deq[fr+1].val(i)) ++fr;
        dp[i] = deq[fr].val(i) + A[i] - B*i*i;
        Line l(2*B*i, dp[i] - B*i*i, i);
        while (bk - fr >= 2 and check(deq[bk-2], deq[bk-1], l, i+K-1)) --bk;
        deq[bk++] = l;
    }

    printf("%lld\n", dp[N-1]);
}