全ての \(l\) について評価値を求めることができればそれらの最大値を取ることでこの問題に正解できます。
今回の問題ではそれが可能なので、その方法を説明します。

• 評価値のうち、区間内の値の総和の部分は累積和を用いることで (時間計算量 \(O(N)\) の予計算のもと) 時間計算量 \(O(1)\) で求めることができます。
• 評価値のうち、区間内の最小値の部分は segment tree を用いることで (時間計算量 \(O(N)\) の予計算のもと) 時間計算量 \(O(\log N)\) で求めることができます。
  • また、スライド最小値などを利用して時間計算量ならし \(O(1)\) で求めることもできます。

あとは、区間和と区間最小とを組み合わせて評価値を計算し、それらの最大値を出力すればよいです。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using ll=long long;
using pl=pair<ll,ll>;

ll op_min(ll a,ll b){return min(a,b);}
ll e_min(){return 1e18;}

int main(){
  ll N,W,K;
  cin >> N >> W >> K;
  vector<ll> A(N+1);
  vector<ll> s(N+1,0);
  vector<pl> vp;
  for(ll i=1;i<=N;i++){
    cin >> A[i];
    vp.push_back({A[i],i});
    s[i]=s[i-1]+A[i];
  }
  segtree<ll,op_min,e_min> smin(A);
  ll res=-8e18;
  for(ll l=1;l<=N-W+1;l++){
    ll sum=(s[l+W-1]-s[l-1]);
    ll minv=smin.prod(l,l+W);
    res=max(res,sum+K*minv);
  }
  cout << res << "\n";
  return 0;
}