ある区間 \(A_l,A_{l+1},\dots,A_r\)に乗算を行った際、 \(\sum A\) ( \(A\) の総和 ) の値は \(A_1+A_2+\dots+A_N + (C-1)(A_l+A_{l+1}+\dots+A_r)\) となります。

この式からわかるように、

• \(C \ge 1\) なるとき \((A_l+A_{l+1}+\dots+A_r)\) を最大化
• \(C<1\) なるとき \((A_l+A_{l+1}+\dots+A_r)\) を最小化

すべきです。

\((A_l+A_{l+1}+\dots+A_r)\) の最大値は以下の通り求めることができます。

• 答え \(=0\) と初期化する。これは操作を一度も行わない場合に対応する。
• 累積和 \(s=0\) 、累積和のうち最小のもの \(m=0\) と初期化する。
• \(i=1,2,\dots,N\) について以下を繰り返す。
  • \(s = s + A_i\) とする。
  • \(m = \min(m,s)\) とする。
  • 答え \(= \max(\) 答え , \(s-m)\) とする。

最小値についても同様のアルゴリズムが適用できます。
これを利用して、この問題に時間計算量 \(O(N)\) で正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

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

  long long n,c;
  cin >> n >> c;
  vector<long long> a(n);
  for(auto &nx : a){cin >> nx;}

  long long tot=0;
  for(auto &nx : a){tot+=nx;}

  if(c>=1){
    // maximum subseg
    long long del=0;
    long long l=0,h=0;
    for(auto &nx : a){
      h+=nx;
      l=min(l,h);
      del=max(del,h-l);
    }
    tot+=del*(c-1);
  }
  else{
    // minimum subseg
    long long del=0;
    long long l=0,h=0;
    for(auto &nx : a){
      h+=nx;
      l=max(l,h);
      del=min(del,h-l);
    }
    tot+=del*(c-1);
  }

  cout << tot << "\n";
  return 0;
}