B. Marvolo Gaunt's Ring 前缀后缀

B. Marvolo Gaunt's Ring

这种一般只有三个的都可以处理前缀和后缀，再枚举中间这个值。

这个和之前写过的C. Four Segments 前缀后缀 处理方式很像。

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <vector>

#include <iostream>

#include <string>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

ll a[maxn], pre[maxn], endss[maxn];

int main()

{

    ll n, p, q, r;

    cin >> n >> p >> q >> r;

    for (int i = ; i <= n + ; i++) endss[i] = pre[i] = -inf64;

    for (int i = ; i <= n; i++) scanf("%lld", &a[i]);

    for (int i = ; i <= n; i++) {

        pre[i] = max(pre[i - ], a[i] * p);

    }

    for (int i = n; i >= ; i--) {

        endss[i] = max(endss[i + ], a[i] * r);

    }

    ll ans = -inf64;

    for (int i = ; i <= n; i++) {

        ans = max(ans, pre[i] + endss[i] + q * a[i]);

        // printf("i=%d pre[%d]=%lld endss[%d]=%lld ans=%lld\n", i, i, pre[i], i, endss[i], ans);

    }

    printf("%lld\n", ans);

    return ;

}