Overview

This is a problem about maximizing the number of smartphones that are still powered on after \(Y\) hours have passed. Since up to \(K\) smartphones can have their battery consumption negated by connecting them to mobile batteries, the key is deciding which smartphones to connect to mobile batteries.

Analysis

First, let’s organize the conditions for each smartphone \(i\) to be usable after \(Y\) hours, for the cases of “not connected” and “connected” to a mobile battery.

1. When not connected to a mobile battery The remaining battery after \(Y\) hours is \(A_i - Y\) %. It is usable if this is greater than \(L\) %. That is, the condition is \(A_i - Y > L \iff A_i > L + Y\).
2. When connected to a mobile battery The remaining battery stays at \(A_i\) %. It is usable if this is greater than \(L\) %. That is, the condition is \(A_i > L\).

Based on these conditions, we classify the smartphones into the following three types:

• Type A (\(A_i > L + Y\)): Usable after \(Y\) hours even without connecting to a mobile battery.
• Type B (\(L < A_i \le L + Y\)): Will power off after \(Y\) hours on its own, but becomes usable if connected to a mobile battery.
• Type C (\(A_i \le L\)): Already powered off or at \(L\) % or below even with a mobile battery connected, so it will definitely be unusable after \(Y\) hours.

As a maximization strategy, it is optimal to preferentially allocate the \(K\) mobile battery slots to Type B smartphones, which are the ones where “connecting changes the outcome.” This is because Type A smartphones are counted regardless of connection, and Type C smartphones are not counted even with connection.

Algorithm

1. Count the number of Type A smartphones count_a and the number of Type B smartphones count_b.
2. Among Type B smartphones, at most \(K\) can be saved by mobile batteries. Therefore, the number that can be saved is \(\min(K, \text{count\_b})\).
3. The final answer is count_a (the number usable without doing anything) + \(\min(K, \text{count\_b})\) (the number made usable by batteries).

Complexity

• Time complexity: \(O(N)\)
  • Since we check and classify each of the \(N\) battery levels once, the computation finishes in time proportional to the input size.
• Space complexity: \(O(N)\)
  • This is the complexity when storing the \(N\) input battery levels in a list.

Implementation Notes

• Boundary conditions: Note that from the condition “the phone powers off when it drops to \(L\) % or below,” being usable requires “strictly greater than \(L\) % (\(A_i > L\)).”

• Wasteful connections: Even when \(K\) is very large, there is no benefit to using more mobile batteries than the total number of Type B smartphones. Therefore, it is necessary to take min(k, count_b).

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを取得し、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 各変数を整数としてパースします
    # N: スマートフォンの台数
    # L: バッテリー残量の閾値（L%以下で電源が切れる）
    # K: モバイルバッテリーに同時に接続できる最大台数
    # Y: 経過時間（時間）
    n = int(input_data[0])
    l = int(input_data[1])
    k = int(input_data[2])
    y = int(input_data[3])
    
    # 各スマートフォンの現在のバッテリー残量 A_i
    a = list(map(int, input_data[4:]))
    
    # スマートフォンが Y 時間後に使用可能であるための条件を考えます。
    # 1. モバイルバッテリーに接続しない場合：
    #    Y 時間後のバッテリー残量は A_i - Y % です。
    #    使用可能である条件は A_i - Y > L、つまり A_i > L + Y です。
    
    # 2. モバイルバッテリーに接続する場合：
    #    バッテリー残量は A_i % のまま維持されます。
    #    使用可能である条件は A_i > L です。
    
    # スマートフォンを以下の3つのタイプに分類します：
    # タイプA: A_i > L + Y
    #   モバイルバッテリーに接続しなくても Y 時間後に使用可能。
    # タイプB: L < A_i <= L + Y
    #   モバイルバッテリーに接続した場合のみ Y 時間後に使用可能。
    # タイプC: A_i <= L
    #   現在すでに電源が切れているか、接続しても L% 以下なので使用不可。
    
    count_a = 0
    count_b = 0
    
    threshold_a = l + y
    threshold_b = l
    
    for val in a:
        if val > threshold_a:
            count_a += 1
        elif val > threshold_b:
            count_b += 1
            
    # 使用可能なスマートフォンの数を最大化するには、
    # 接続枠 K を優先的にタイプBのスマートフォンに割り当てます。
    # タイプAは接続しなくてもカウントされ、タイプCは接続してもカウントされません。
    
    # タイプBのうち、救済できるのは最大で K 台です。
    saved_b = min(k, count_b)
    
    # 合計の最大台数は (タイプAの総数) + (救済したタイプBの数) となります。
    ans = count_a + saved_b
    
    # 結果を出力します
    print(ans)

if __name__ == '__main__':
    main()

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