Overview

Given \(N\) smartphones, find the maximum number that can still be used after \(Y\) hours, when you can connect up to \(K\) of them to a mobile battery.

Analysis

First, consider the relationship between each smartphone’s battery level \(A_i\), the consumption of \(Y\)% after \(Y\) hours, and the threshold \(L\)% at which the phone turns off.

• Without using a mobile battery, the condition to still be usable after \(Y\) hours is: $\(A_i - Y > L\)\( In other words, \)\(A_i > L + Y\)$ must be satisfied.

Smartphones satisfying this condition can survive even without a mobile battery.

On the other hand, smartphones satisfying $\(L < A_i \leq L + Y\)\( will run out of battery and become unusable after \)Y$ hours if left as is, so they are worth “saving” with a mobile battery.

Conversely, smartphones with $\(A_i \leq L\)$ already have too little battery — they are either already unusable or will turn off immediately, so using a mobile battery on them is pointless.

Therefore, the strategy is:

1. Smartphones with \(A_i > L + Y\) survive automatically, so count them.
2. Among smartphones with \(L < A_i \leq L + Y\), “save” up to \(K\) of them with mobile batteries.
3. Since we can save at most \(K\) phones, it is optimal to sort the smartphones in this range by battery level in descending order and select the top \(K\).

By classifying this way, we can efficiently find the answer without exhaustive search.

Algorithm

1. Read the input.
2. Count the number of smartphones satisfying \(A_i > L + Y\) (survive_without_powerbank).
3. List the smartphones satisfying \(L < A_i \leq L + Y\) and sort them in descending order.
4. Count up to \(K\) phones from the above list as “saveable”.
5. The sum of steps 2 and 4 is the answer.

Complexity

• Time complexity: \(O(N \log N)\) (due to sorting)
• Space complexity: \(O(N)\) (size of the list can_be_saved)

Implementation Notes

• Using list comprehensions to extract elements matching the conditions is concise.

• Sort in descending order to prioritize smartphones with higher remaining battery for mobile battery usage.

• Use min(K, len(can_be_saved)) to accurately calculate the number that can actually be saved.

  Source Code

import heapq

N, L, K, Y = map(int, input().split())
A = list(map(int, input().split()))

# モバイルバッテリーを使わない場合、Y時間後に使える条件は A[i] > L + Y
# しかし、モバイルバッテリーをK台まで接続できるので、それを利用して最適化する

# 各スマホについて、Y時間後に使えるかどうかを判定
# モバイルバッテリーを使っても使わなくても、バッテリーがL以下になると切れる
# モバイルバッテリーを使っていないスマホはY時間後に A[i] - Y > L であればよい
# つまり A[i] > L + Y

# モバイルバッテリーを使うことで無限に使えるようになるので、
# モバイルバッテリーを使うべきは、Y時間後に自然に切れてしまうスマホ

# まず、モバイルバッテリーを使わずにY時間後に生き残るスマホの数を数える
survive_without_powerbank = sum(1 for a in A if a > L + Y)

# モバイルバッテリーを使ってY時間後に生き残れるスマホの数を調べる
# 条件：A[i] > L （そうでないと最初から使えない or すぐに切れる）
# そして、A[i] <= L + Y （すでに生き残れるならモバイルバッテリー不要）

can_be_saved = [a for a in A if L < a <= L + Y]
can_be_saved.sort(reverse=True)  # 大きい順（バッテリーが多いものを優先的に救う）

# モバイルバッテリーで救えるのは最大K台
saved_by_powerbank = min(K, len(can_be_saved))

# 結果：自然に生き残るスマホ + モバイルバッテリーで救えるスマホ
result = survive_without_powerbank + saved_by_powerbank
print(result)

This editorial was generated by qwen3-coder-480b.