\(f\) を \(1\) 回計算するだけなら，左端から取れるだけとる貪欲を行えばよいです．

\(f\) をすべての区間について計算するために，各 \(l\) について，そこから貪欲を走らせた際の様子を考えます．

各 \(i\) について，\(A_i+\cdots+A_j>S\) となる最小の \(j\) を \(p_i\) とおくことにします（そのような \(j\) が存在しない場合は \(p_i=N+1\) とします）．

\(dp[i]=\sum_{i \leq r}f(A[i,r])\) と定義します． 便利のため，\(dp[N+1]=0\) とします．

\(i=N,N-1,\cdots,1\) について \(dp[i]\) を求めていきます．

\(\sum_{i \leq r}f(A[i,r])\) を，\(r<p_i\) と \(p_i \leq r\) に分けて考えます． まず \(r<p_i\) については，\(f(A[i,r])=1\) とすぐにわかるのでよいです． \(p_i \leq r\) については，上記の貪欲を考えると，まず区間 \([i,p_i-1]\) を取り，その後 \(p_i\) から貪欲をスタートする形になります． \(p_i\) からスタートした結果というのは，\(dp[p_i]\) にほかならないです．以上をまとめると，\(dp[i]=dp[p_i]+(N+1-i)\) とわかります．

上の操作をそのまま実装すれば，\(O(N)\) や \(O(N \log N)\) 時間の解法が得られます．

解答例