Brute force with prefix Sum


#1
int n = A.size(); int sum[n+1]; sum[0] = 0;
for(int i=1;i<=n; i ++) sum[i] = sum[i-1] + A[i-1];
int ans = 0;
for(int i=0;i<n;i++)
{
    for(int j=i;j<n;j++)
    {
        if(sum[j+1] - sum[i] < B) ans++;
    }
}
return ans;

As n <= 10^ 4 , an O(n^2) solution will be accepted as max number of operations in the worst case = (5*10^7) which can be easily done under 1 second


#2

Hey, thanks for sharing your approach … its interesting to solve with prefix sum
However python implementation fails !!