この問題は、 尺取り法 を使うことで高速に解くことができます。

\(l=1,2,\dots,N\) それぞれに対し、以下を高速に求めることを考えます。

• \(A_l+A_{l+1}+\dots+A_r \le K\) となる最大の \(r\)

これが分かれば、左端が \(l\) のときにありうる右端は \(l,l+1,\dots,r\) であり、 ( \(A_i \ge 1\) であることから ) これらに限られることが分かります。

この \(r\) は、 \(l\) が増えていくにつれて(広義)単調増加、つまり \(r\) も増えていきます。なので、以下の解法が成立します。

• \(s=0,r=0\) と初期化する。
• \(l=1,2,\dots,N\) について、以下を繰り返す。
  • \(s+A_{r+1} \le K\) かつ \(r+1 \le N\) である限り、以下を繰り返す。
    • \(r\) に \(1\) 加算する。その後、 \(s\) に \(A_r\) 加算する。
  • この時点での \(r\) が現在の \(l\) に対して求めたい \(r\) である。
  • \(s\) から \(A_l\) 減算する。

変数 \(s\) が \(A_l+A_{l+1}+\dots+A_r\) の値を常に保持しているような感じです。

このように、 \(l\) が増えていくにつれて \(r\) が(広義)単調増加であることを利用すると、 \(l,r\) ともに全体で一度だけ \(0,1\) から \(N\) まで動かせばよいので、全体で時間計算量 \(O(N)\) で欲しい \(r\) が求まるということになります。

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

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

using ll=long long;

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