B. Marvolo Gaunt's Ring ～range min, range maxができる構造体で殴る～

• Quiz
  • https://codeforces.com/problemset/problem/855/B
• AC
  • https://codeforces.com/contest/855/submission/100722877
• 解説
  • 3つ組の真ん中を固定した時、左右でどれを選べばいいかは範囲min, 範囲maxが取れれば分かる
  • 左からのmin, max配列
  • 右からのmin, max配列
  • を持ってもいいが、セグ木で殴るをしてみた

#include <atcoder/lazysegtree>
using namespace atcoder; // 忘れがち

// min, max共通
using S = long long;
using F = long long;
const S INF = 8e18;

// min
S op(S a, S b){ return std::min(a, b); }
S e(){ return INF; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

// max
S op2(S a, S b){ return std::max(a, b); }
S e2(){ return -INF; }
S mapping2(F f, S x){ return f+x; }
F composition2(F f, F g){ return f+g; }
F id2(){ return 0; }

// 範囲内のmin, maxがとれます
struct RangeMinMax{
    lazy_segtree<S, op, e, F, mapping, composition, id> segMin;
    lazy_segtree<S, op2, e2, F, mapping2, composition2, id2> segMax;
    RangeMinMax(VI V){
      segMin = lazy_segtree<S, op, e, F, mapping, composition, id>(V);
      segMax = lazy_segtree<S, op2, e2, F, mapping2, composition2, id2>(V);
    }
    ll min(ll l, ll r){
      return segMin.prod(l,r);
    }
    ll max(ll l, ll r){
      return segMax.prod(l,r);
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;cin>>N;
    VI C(3);
    rep(i,3)cin>>C[i];

    VI A(N);
    rep(i, N) cin >> A[i];

    auto range = RangeMinMax(A);

    ll ma=-8*inf;
    FOR(i,0,N){
      // 真ん中がjのとき
      ll value = A[i]*C[1];
      // 左
      if(C[0]>0){
        value += C[0] * range.max(0,i+1);
      }else{
        value += C[0] * range.min(0,i+1);
      }
      // 右
      if(C[2]>0){
        value += C[2] * range.max(i,N);
      }else{
        value += C[2] * range.min(i,N);
      }
      chmax(ma,value);
    }
    p(ma);
    
    return 0;
}