Overview

This problem asks us to find the number of ways to choose \((l, r)\) such that the total weight of a contiguous subsequence does not exceed the minimum bag capacity \(C_{\min}\). We efficiently count these using the two pointers technique (sliding window).

Analysis

Essence of the Problem

There are \(M\) bag capacities, but the only one that matters is the minimum value \(C_{\min} = \min(C_1, \ldots, C_M)\). Therefore, the problem can be rephrased as follows:

Find the number of pairs \((l, r)\) (\(1 \leq l \leq r \leq N\)) satisfying \(W_l + W_{l+1} + \cdots + W_r \leq C_{\min}\).

Naive Approach and Its Issues

If we enumerate all pairs \((l, r)\), there are \(O(N^2)\) pairs, and computing the sum for each takes \(O(N^3)\) in the worst case. Using prefix sums reduces this to \(O(N^2)\), but with \(N \leq 5 \times 10^5\), we get \(N^2 = 2.5 \times 10^{11}\), which is far too slow.

Key Observation: Monotonicity

Since all candy weights are positive (\(W_i \geq 1\)), the following property holds:

• When \(r\) is fixed, decreasing \(l\) increases the sum (because more candies are included).
• If the sum exceeds \(C_{\min}\) for some \(l\), it will also exceed \(C_{\min}\) for any smaller \(l\).

Because of this monotonicity, we can use the two pointers technique.

Algorithm

We solve this using the two pointers technique.

1. Compute \(C_{\min} = \min(C_1, \ldots, C_M)\).
2. Initialize left = 0 (0-indexed), current_sum = 0, ans = 0.
3. Move right from \(0\) to \(N-1\), performing the following:
   • Add \(W[\text{right}]\) to current_sum.
   • While current_sum > C_{\min}, subtract \(W[\text{left}]\) from current_sum and increment left by \(1\).
   • At this point, all intervals from \([\text{left}, \text{right}]\) to \([\text{right}, \text{right}]\) satisfy the condition. The count is \(\text{right} - \text{left} + 1\), so add it to ans.

Concrete Example

For \(N=4\), \(W = [3, 1, 4, 1]\), \(C_{\min} = 5\):

right	Added	current_sum	left movement	Valid intervals	Count
0	3	3	none	[0,0]	1
1	1	4	none	[0,1],[1,1]	2
2	4	8→5	left: 0→1	[1,2],[2,2]	2
3	1	6→2	left: 1→2	[2,3],[3,3]	2

The answer is \(1+2+2+2 = 7\) ways.

Complexity

• Time complexity: \(O(N + M)\)
  • Computing \(C_{\min}\) takes \(O(M)\), and the two pointers technique takes \(O(N)\) (both left and right advance at most \(N\) times each).
• Space complexity: \(O(N + M)\)
  • Required for storing arrays \(W\) and \(C\).

Implementation Notes

• \(C_j\) values can be up to \(10^{18}\), which is very large, so care must be taken to ensure prefix sums fit within 64-bit integers. Python handles this automatically with arbitrary-precision integers, but in C++ and similar languages, long long must be used.

• Fast input: Since \(N, M\) can be up to \(5 \times 10^5\), in Python we speed up input by reading all at once with sys.stdin.buffer.read().

• In the two pointers technique, left never exceeds right. Since all \(W_i \geq 1\) and \(C_{\min} \geq 1\), it is guaranteed that at least an interval of length 1 (a single candy) always satisfies the condition.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    W = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(M)]; idx += M
    
    C_min = min(C)
    
    ans = 0
    current_sum = 0
    left = 0
    for right in range(N):
        current_sum += W[right]
        while current_sum > C_min:
            current_sum -= W[left]
            left += 1
        ans += right - left + 1
    
    print(ans)

main()

---

This editorial was generated by claude4.6opus-thinking.