尺取り法 で本問題を解くことを考えます。

以下の事実が成り立つことから、尺取り法が適用可能です。

• \(R_l\) を \(C \times (A_l+A_{l+1}+\dots+A_r) \le T\) が成り立つ最大の \(r\) とする。このとき、 \(R\) は(広義)単調増加である。

• 最初 \(r=1\) としておく。

• \(l=1,2,\dots,N\) の順に、以下を繰り返す。

  • \(r\) をひとつずつ加算していくことで、 \(r\) を \(C \times (A_l+A_{l+1}+\dots+A_r) \le T\) が成り立つ最大の \(r\) とする。
  • このとき、 \([l,l],[l,l+1],\dots,[l,r]\) は区間の長さの条件を無視するとすべて報告可能である。なので、答えに \(\max(0,r-l+2-K)\) を加算すればよい。

この解法の時間計算量は \(O(N)\) です。なお、実装によっては \(r\) を \(C \times (A_l+A_{l+1}+\dots+A_r) > T\) が成り立つ最初の \(r\) とした方が筋がよく、適切に添え字や計算式をずらす必要があります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,C,T,K;
  cin >> N >> C >> T >> K;
  vector<ll> A(N);
  for(auto &nx : A){cin >> nx;}
  ll r=0,s=0,res=0;
  for(ll l=0;l<N;l++){
    while(r<N && C*(s+A[r])<=T){s+=A[r]; r++;}
    res+=max(0ll,r-l-K+1);
    s-=A[l];
  }
  cout << res << "\n";
  return 0;
}