Overview

This problem asks us to find the number of contiguous intervals of snacks whose total weight is at most the minimum bag capacity.

Analysis

The essence of the problem is to count the number of intervals \((l, r)\) in the sequence \(W_1, W_2, ..., W_N\) such that the sum of the contiguous subsequence is at most \(C_{\min}\).

A naive approach would be to compute the sum for all intervals \((l, r)\) and check the condition, but this has \(O(N^2)\) time complexity, which is too slow given the constraint that \(N\) can be up to \(500,000\).

Instead, we can solve this efficiently using the sliding window method (two-pointer technique). In this approach, we advance the right endpoint \(r\) sequentially while adjusting the left endpoint \(l\) to maintain the condition, efficiently counting the number of valid intervals for each \(r\).

Algorithm

1. Find the minimum bag capacity \(C_{\min}\)
2. Initialize the left pointer left to 0 and set the current interval sum current_sum to 0
3. Advance the right pointer right from 0 to N-1 in order:
   • Add \(W[\text{right}]\) to current_sum
   • While current_sum exceeds \(C_{\min}\), subtract \(W[\text{left}]\) from current_sum while moving the left endpoint to the right
   • At this point, the interval \([\text{left}, \text{right}]\) satisfies the condition, so add the number of valid intervals with right endpoint right, which is (right - left + 1), to the answer

With this approach, each element is processed at most twice (once when added as the right endpoint and once when removed as the left endpoint), making the computation efficient.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Be careful that the left pointer does not exceed right (the condition left <= right)

• When the sum of an interval exceeds \(C_{\min}\), adjust the left endpoint to restore the condition

• By cumulatively adding the number of valid intervals at each step, we can efficiently compute the total count

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    W = list(map(int, data[2:2+n]))
    C_list = list(map(int, data[2+n:2+n+m]))
    
    c_min = min(C_list)
    
    left = 0
    current_sum = 0
    count = 0
    
    for right in range(n):
        current_sum += W[right]
        
        while current_sum > c_min and left <= right:
            current_sum -= W[left]
            left += 1
            
        count += (right - left + 1)
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.