Codeforces 855B(枚举)

Codeforces 855B
题意：给一个数组，求$p \cdot a_i + q \cdot a_j + r \cdot a_k$的最大值$(1 \leq i \leq j \leq k \leq n) $
维护前缀后缀最大值/最小值，然后我们枚举中间值$j$，算每个$j$作为中间点的值
然后$q$的贡献为$q \cdot a_i$
而对于$p$, 如果有$p \geq 0$，那么$p$的贡献为$p \cdot lmax_i$，反之$p$的贡献为$p \cdot lmin_i$
对于$r$, 如果有$r \geq 0$，那么$r$的贡献为$r \cdot rmax_i$，反之$r$的贡献为$r \cdot rmin_i$
然后最后可以得出一个最大的值，即为答案

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
const LL INF = 9223372036854775807;
LL n, p, q, r, a[MAXN], lmax[MAXN], lmin[MAXN], rmax[MAXN], rmin[MAXN];
void clean() {
    for (LL i = 0; i <= n + 1; i++) lmax[i] = rmax[i] = -INF, lmin[i] = rmin[i] = INF;
}
void solve() {
    clean();
    for (LL i = 1; i <= n; i++) scanf("%I64d", &a[i]);
    for (LL i = 1; i <= n; i++) lmax[i] = max(lmax[i - 1], a[i]), lmin[i] = min(lmin[i - 1], a[i]);
    for (LL i = n; i >= 1; i--) rmax[i] = max(rmax[i + 1], a[i]), rmin[i] = min(rmin[i + 1], a[i]);
    LL ans = -INF;
    for (LL i = 1; i <= n; i++) {
        LL tot = q * a[i];
        if (p < 0) tot += p * lmin[i]; else tot += p * lmax[i];
        if (r < 0) tot += r * rmin[i]; else tot += r * rmax[i];
        ans = max(ans, tot);
    }
    printf("%I64d\n", ans);
}
int main() {
    scanf("%I64d%I64d%I64d%I64d", &n, &p, &q, &r), solve();
    return 0;
}