Overview

This problem asks for the maximum number of packages that can be carried out when repeatedly selecting contiguous intervals (with total weight at most \(K\)) from a row of packages. The answer equals “the number of packages whose weight is at most \(K\).”

Analysis

Key Insight: Conditions for a Package to Be Carried Out

First, packages whose weight exceeds \(K\) (\(A_i > K\)) cannot be carried out even by themselves, so they can never be carried out.

Next, we show that packages whose weight is at most \(K\) (\(A_i \leq K\)) can always be carried out.

Why Can Every Package with \(A_i \leq K\) Always Be Carried Out?

In a carry-out operation, we select “a contiguous interval in the currently remaining row.” Selecting just a single package (an interval of length 1) is also allowed.

Therefore, for any package with \(A_i \leq K\), even if it is sandwiched between other packages, we can simply select that single package as an interval and carry it out.

Let’s verify with a concrete example. Suppose the packages are \([3, 100, 5, 100, 2]\) and \(K = 10\):

• \(A_1 = 3 \leq 10\): Can be carried out by selecting just this one package
• \(A_2 = 100 > 10\): Cannot be carried out
• \(A_3 = 5 \leq 10\): Can be carried out by selecting just this one package
• \(A_4 = 100 > 10\): Cannot be carried out
• \(A_5 = 2 \leq 10\): Can be carried out by selecting just this one package

The answer is \(3\).

Isn’t It Better to Carry Out Multiple Packages at Once?

Carrying out multiple packages at once reduces the number of operations, but the problem asks for the maximum number of packages that can be carried out. Since there is no limit on the number of operations, carrying them out one at a time is never a disadvantage.

Conversely, trying to carry out multiple packages at once can only cause the total to exceed \(K\) and make carry-out impossible — it never increases the count.

Conclusion

Maximum number of packages that can be carried out \(=\) the number of indices \(i\) satisfying \(A_i \leq K\)

Algorithm

1. For each package \(A_i\), determine whether \(A_i \leq K\).
2. Count the number of packages satisfying \(A_i \leq K\) and output that count.

Complexity

• Time complexity: \(O(N)\) (just checking each package once)
• Space complexity: \(O(N)\) (for reading the input; can be reduced to \(O(1)\) by reading incrementally)

Implementation Notes

• Since \(K\) and \(A_i\) can be as large as \(10^{18}\), in languages like C++ you need to use long long. In Python, there is no need to worry about integer overflow.

• Although the high degree of freedom in operations makes the problem appear complex at first glance, once you realize the key insight that “carrying out packages one at a time is sufficient,” the implementation becomes very simple.

  Source Code

def main():
    import sys
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    count = 0
    for i in range(N):
        if int(input_data[2 + i]) <= K:
            count += 1
    print(count)

main()

---

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