Overview

Given \(N\) items, we repeatedly select a contiguous subarray whose total weight is at most \(K\) and remove it. The problem asks for the maximum number of items that can ultimately be removed.

Analysis

At first glance, this might seem like a problem requiring complex dynamic programming or simulation to determine “which intervals to select in which order” and “which items become adjacent after closing gaps.” However, by carefully organizing the conditions of the operation, we arrive at a very simple conclusion.

1. Condition for items that cannot be removed If an item has weight \(A_i\) exceeding \(K\) (i.e., \(A_i > K\)), then any contiguous subarray containing that item will necessarily have a total weight exceeding \(K\). Therefore, items with weight greater than \(K\) can never be removed.

2. Condition for items that can be removed Conversely, if an item has weight \(A_i \le K\), that item can always be removed. This is because the removal operation allows selecting “one or more contiguous items,” so we can simply select that single item as the interval, giving a total weight of \(A_i \le K\), which satisfies the condition.

3. Relationship between operation order and count Due to the rule that “gaps are closed after items are removed,” items that were originally separated may become adjacent and can potentially be removed together. However, what this problem asks for is the maximum number of items that can be removed. Whether we remove items in bulk or one by one, the total number of items that can ultimately be removed does not change. Furthermore, removing one item never causes another item that could have been removed to become impossible to remove.

From the above, the answer to this problem is simply “the number of items whose weight is at most \(K\)”.

Algorithm

1. Read the number of items \(N\) and the upper limit \(K\).
2. Examine the array of item weights \(A\) in order.
3. For each \(A_i\), if \(A_i \le K\), increment the count by 1.
4. Output the final count.

Complexity

• Time complexity: \(O(N)\) We scan and compare each of the \(N\) items once, so the computation finishes in linear time. This is sufficiently fast under the constraint \(N \le 2 \times 10^5\).
• Space complexity: \(O(N)\) We use \(O(N)\) memory to store the input item weights in a list.

Implementation Notes

• Fast input: Since \(N\) can be large, in Python using sys.stdin.read().split() to read all input at once can reduce execution time.

• Type conversion: Since input is read as strings, it must be converted to integers using int() before performing comparisons.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリストにする
    # sys.stdin.read().split() は高速な入力読み込み方法です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合や制約に満たない場合のガード
    if len(input_data) < 2:
        return
    
    # 荷物の数 N とトラックの積載量上限 K を取得
    N = int(input_data[0])
    K = int(input_data[1])
    
    # 荷物の重さのリストを取得（インデックス 2 以降）
    A = input_data[2:]
    
    # 搬出できる荷物の最大数をカウントする
    # 各荷物について、その重さが K 以下であれば、単独で搬出することが可能です。
    # 逆に、重さが K を超える荷物は、どのような連続区間に含まれていても
    # その区間の合計重さが K を超えてしまうため、決して搬出できません。
    # 「荷物を取り除いた後に詰め直す」というルールがありますが、
    # 最終的に搬出できる荷物の数は、各荷物が単独で K 以下であるかどうかにのみ依存します。
    
    removable_count = 0
    # N 個の荷物について順番に判定を行う
    # N は最大 2 * 10^5 であるため、O(N) のループで十分に高速です
    for i in range(N):
        if int(A[i]) <= K:
            removable_count += 1
            
    # 搬出できる荷物の最大数を出力
    print(removable_count)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.