Overview

This problem asks for the maximum number of items that can be removed, given that in each operation you can remove a “contiguous subarray with total weight at most \(K\).” The conclusion is that the answer is the number of items satisfying \(A_i \le K\).

Analysis

The key observations are the following two points (the constraint that \(A_i \ge 1\) are positive integers is crucial).

1. Items with \(A_i > K\) can never be removed

In any removal operation, the total weight of the chosen subarray must be at most \(K\).
However, if you choose a subarray containing an item with \(A_i > K\), the total of that subarray is at least \(A_i\), which necessarily exceeds \(K\) (since all other items are positive, adding them only increases the total).

Therefore, items with \(A_i > K\) cannot be removed by any operation.

2. Items with \(A_i \le K\) can always be removed

Conversely, if \(A_i \le K\), you can choose the subarray consisting of just that single item (length 1), and the total is \(A_i \le K\), so it is removable on its own.
You can repeat this for all items with \(A_i \le K\). Even though the sequence gets compressed and adjacency relationships change as items are removed, the “select individually” strategy is unaffected.

From the above: - Items that cannot be removed: \(A_i > K\) - Items that can always be removed: \(A_i \le K\)

So the maximum number of removed items is the count of \(A_i \le K\).

(Example) \(K=5,\ A=[2,7,3,10,5]\)
\(7\) and \(10\) exceed \(K\), so they are impossible to remove. \(2, 3, 5\) can each be removed individually, so the maximum is \(3\).

Why a naive approach is unnecessary

At first glance, since we are “choosing subarrays,” one might want to think about greedy or DP approaches to find the optimal way to select subarrays. However, from the observations above, no matter how cleverly you choose subarrays, you cannot remove items with \(A_i > K\), so the problem reduces to a simple count.
Therefore, subarray searching or simulation (worst case \(O(N^2)\), etc.) is excessive and wasteful given the constraint \(N \le 2\times 10^5\).

Algorithm

1. Scan array \(A\) from left to right.
2. If \(A_i \le K\), increment the count by 1.
3. Output the count.

This gives the maximum number of removed items (each item can be removed individually, and \(A_i > K\) is impossible).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (no additional array needed if input is processed sequentially)

Implementation Notes

• \(K\) and \(A_i\) can be up to \(10^{18}\), but Python’s int handles this natively.

• By using A = map(int, input().split()) for sequential scanning, you can concisely count with sum(1 for x in A if x <= K).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = map(int, input().split())
    ans = sum(1 for x in A if x <= K)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.