Overview

This is a problem of finding how many ways there are to select a contiguous subsequence from a sequence \(W\) such that its sum is at most the minimum value of \(C\).

Analysis

In this problem, we need to select a “contiguous interval” \([l, r]\) from the sequence of candy weights \(W_1, W_2, \ldots, W_N\), and count the number of such intervals whose sum is at most the minimum bag capacity \(C_{\min}\).

A naive approach would be to enumerate all intervals \([l, r]\) and compute their sums, which would give the correct answer but requires \(O(N^2)\) computation. Given the constraint \(N \leq 5 \times 10^5\), this clearly won’t finish in time.

Therefore, we use prefix sums to efficiently compute interval sums. Additionally, to efficiently count the number of intervals satisfying the condition, we use a technique called the two pointers method.

In the two pointers method, for a fixed right endpoint \(r\), we dynamically track how far left the left endpoint \(l\) can extend, counting the number of intervals that satisfy the condition. This allows us to determine the valid range of \(l\) for each \(r\) in \(O(1)\), solving the entire problem in \(O(N)\) time.

Algorithm

1. First, compute the minimum bag capacity \(C_{\min} = \min(C_1, C_2, \ldots, C_M)\).
2. Next, compute the prefix sum array \(S\) of the candy weight sequence \(W\):
   • \(S[i] = W_1 + W_2 + \cdots + W_i\)
   • By setting \(S[0] = 0\), the sum of interval \([l, r]\) can be computed as \(S[r] - S[l-1]\).
3. Using the two pointers method, find the maximum left endpoint \(l\) satisfying the condition for each right endpoint \(r\):
   • Find the maximum \(l\) such that \(S[r] - S[l] \leq C_{\min}\).
   • At this point, all intervals \([l+1, r], [l+2, r], \ldots, [r, r]\) satisfy the condition, so add \(r - l\) to the answer.

Complexity

• Time complexity: \(O(N + M)\)
  • Computing the minimum takes \(O(M)\), and the two pointers method takes \(O(N)\).
• Space complexity: \(O(N + M)\)
  • Arrays are needed to store the input and the prefix sum array.

Implementation Notes

• When computing the prefix sum, prepending a \(0\) at the beginning simplifies the interval sum calculation.

• In the two pointers method, we advance the right endpoint one step at a time while advancing the left endpoint until the condition is no longer satisfied, enabling efficient counting.

• Note that the sum of interval \([l, r]\) is \(S[r] - S[l-1]\), and be careful with index management in the code.

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    W = list(map(int, data[2:2+N]))
    C = list(map(int, data[2+N:2+N+M]))
    
    # 袋の最小耐荷重を求める
    C_min = min(C)
    
    # 累積和を計算
    S = [0] + list(accumulate(W))
    
    # 尺取り法 (two pointers) で条件を満たす区間の数を数える
    count = 0
    left = 0
    
    for right in range(1, N+1):
        # 区間 [left+1, right] の和が C_min 以下になるまで left を進める
        while S[right] - S[left] > C_min:
            left += 1
        # この時点で [left+1, right], [left+2, right], ..., [right, right] がすべて条件を満たす
        count += right - left
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.