When multiplying a certain interval \(A_l,A_{l+1},\dots,A_r\), the value of \(\sum A\) (the sum of \(A\)) becomes \(A_1+A_2+\dots+A_N + (C-1)(A_l+A_{l+1}+\dots+A_r)\).

As can be seen from this formula,

• When \(C \ge 1\), we should maximize \((A_l+A_{l+1}+\dots+A_r)\).
• When \(C < 1\), we should minimize \((A_l+A_{l+1}+\dots+A_r)\).

The maximum value of \((A_l+A_{l+1}+\dots+A_r)\) can be found as follows:

• Initialize the answer to \(0\). This corresponds to the case where the operation is not performed at all.
• Initialize the cumulative sum \(s=0\), and the minimum of the cumulative sums \(m=0\).
• Repeat the following for \(i=1,2,\dots,N\):
  • Set \(s = s + A_i\).
  • Set \(m = \min(m,s)\).
  • Update the answer to \(\max(\) answer, \(s-m)\).

The same algorithm can be applied to find the minimum value as well.
By utilizing this, the problem can be solved in time complexity \(O(N)\).

Sample Implementation (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;
}