Overview

The bag’s weight capacity is fixed at \(C_{\min}=\min(C_1,\dots,C_M)\), so the problem reduces to counting “how many contiguous subsequences \((l,r)\) have a total weight of at most \(C_{\min}\).”

Analysis

Since only the bag with the minimum capacity remains relevant, the only condition we need to check is: $\(W_l+W_{l+1}+\cdots+W_r \le C_{\min}\)\( Therefore, after computing \)C{\min}\(, we just need to count the number of contiguous intervals in the array \)W\( whose partial sum is at most \)C{\min}$.

Naively trying all pairs \((l,r)\) gives up to \(N(N+1)/2\) pairs, which is \(O(N^2)\) for \(N\le 5\times 10^5\) and will certainly TLE.

The key observation here is that \(W_i \ge 1\) (all values are positive). For an array of only positive numbers:

• Extending the right endpoint \(r\) to the right increases the interval sum (it never stays the same)
• Shrinking the left endpoint \(l\) to the right decreases the interval sum

This monotonicity allows us to count everything in \(O(N)\) using the Two Pointers / Sliding Window technique.

As a concrete example, consider \(W=[2,1,3,2],\ C_{\min}=4\): - When \(l=0\), extending as far as possible gives \([2,1]\) (sum 3); adding 3 would make it 6, which exceeds the limit, so we stop → the valid right endpoints are \(r=0,1\), giving 2 intervals - Then we advance to \(l=1\) and similarly “extend the right endpoint as far as possible” In this way, we can count all intervals without ever moving the right endpoint backward.

Algorithm

1. Compute \(C_{\min}=\min(C_1,\dots,C_M)\) from the input.
2. Use the two-pointer technique, maintaining for each left endpoint \(l\) the “next position past the maximum valid right endpoint \(r\).”
   • Variables:
     • l: left endpoint (loop from 0 to \(N-1\))
     • r: the “next” position past the right endpoint (considering the half-open interval \([l,r)\))
     • s: current interval sum \(W_l+\cdots+W_{r-1}\)
   • Procedure:
     1. while r < N and s + W[r] <= Cmin: — while this holds, advance r and add to s (extend as far as possible).
     2. For the fixed l, the intervals satisfying the condition are: $\([l,l], [l,l+1], \dots, [l,r-1]\)\( which is **\)(r-l)$ intervals**, so add r - l to the answer.
     3. To move to the next l+1, we normally do s -= W[l] to remove the left endpoint.
     4. However, if r == l (i.e., the interval has length 0, meaning even \(W_l\) alone doesn’t fit), there is nothing to subtract from s, so we advance r by 1 to prevent the loop from getting stuck (the if r == l: r += 1 in the code).

In this approach, r increases at most \(N\) times in total, so the entire process runs in linear time.

Complexity

• Time complexity: \(O(N+M)\) (\(O(M)\) for computing \(C_{\min}\), \(O(N)\) for the two-pointer technique)
• Space complexity: \(O(N)\) (storing the weight array \(W\))

Implementation Notes

• \(W_i\) can be large and \(C_{\min}\) can be up to \(10^{18}\), so the interval sum s requires 64-bit integers (in Python this is handled naturally).

• The maximum possible answer is \(N(N+1)/2\), which is approximately \(1.25\times 10^{11}\) when \(N=5\times 10^5\), so this also requires 64-bit integers (in Python this is fine).

• If the r == l case (where even a single element doesn’t fit, i.e., \(W_l > C_{\min}\)) is not handled, l would advance while r stays stuck. As shown in the code, we advance r to ensure the loop makes progress.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    W = [next(it) for _ in range(N)]
    Cmin = min(next(it) for _ in range(M))

    r = 0
    s = 0
    ans = 0

    for l in range(N):
        while r < N and s + W[r] <= Cmin:
            s += W[r]
            r += 1
        ans += r - l
        if r == l:
            r += 1
        else:
            s -= W[l]

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.