以下の通りに水をまくのが最善です。

• \(i=1,2,\dots,N\) の順に花壇を調べる。
  • もし現在の水分量が \(T\) に満たなければ、花壇 \(i\) に足りない分の水をやる必要がある。この時点で花壇 \(i-1\) 以前について水分量は十分なので、花壇 \(i,i+1,\dots,i+K-1\) に足りない分だけ水をやる。

花壇 \(i,i+1,\dots,i+K-1\) に水を \(w\) だけやるという操作が難しいですが、 imos法 の要領で以下の操作に帰着させることができます。

• 既にやった水分量に \(w\) 加算する
• 花壇 \(i+K\) に着目し始めるタイミングで、既にやった水分量から \(w\) 減算する

こうすることで、花壇 \(i,i+1,\dots,i+K-1\) に水を \(w\) やった状況を作り出すことができます。

詳細は実装例も参照してください。

時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll n,k,t,c;
  cin >> n >> k >> t >> c;
  vector<ll> a(n);
  for(auto &nx : a){cin >> nx;}

  ll water=0,res=0;
  vector<ll> finish(n+k+5,0);
  for(ll i=0;i<n;i++){
    water-=finish[i];

    ll start=max(0ll,t-a[i]-water);
    res+=start;
    water+=start;
    finish[i+k]+=start;
  }
  cout << res*c << "\n";
  return 0;
}