Count Subarrays With Score Less Than K

Count the number of non-empty contiguous subarrays of a positive-integer array whose score—defined as (sum of elements) × (subarray length)—is strictly less than k. With n up to 1e5 and values/k large, you need an algorithm substantially faster than brute-force O(n^2).