Overview

To maximize the number of smartphones that are still powered on after \(Y\) hours, we count “smartphones that survive without doing anything” and “smartphones that survive if connected to a mobile battery,” then compute the answer.

Analysis

First, a smartphone connected to a mobile battery does not lose any charge at all, so it will definitely be usable after \(Y\) hours as long as “it is not already powered off at this moment.”
On the other hand, a smartphone that is not connected loses \(1\%\) per hour, so after \(Y\) hours its battery will be \(A_i - Y\).

An important point to note is that “the phone powers off at the exact moment it reaches \(L\%\).”
Therefore, the conditions for a smartphone to be usable after \(Y\) hours are: - If not connected: \(A_i - Y > L\) (at exactly \(=\) it powers off at that moment) - If connected: since it doesn’t decrease, \(A_i > L\) (if it’s already at \(L\) or below, it’s already unusable)

Thus, each smartphone can be classified into one of the following 3 categories:

1. Survives without doing anything
   \(A_i > L + Y\)
   → No connection needed; still usable after \(Y\) hours

2. Survives if connected
   \(L < A_i \le L + Y\)
   → Without connection, it will drop to \(L\) or below partway through and power off, but with connection it doesn’t decrease so it remains usable

3. Impossible no matter what
   \(A_i \le L\)
   → Already unusable at this moment (connecting it won’t revive it)

Therefore, the optimal strategy is simple: connect the smartphones in category (2) “up to a maximum of \(K\) units” to save them.
Category (1) is already safe from the start, and category (3) cannot be saved.

There is no need to search for “which ones to connect” or to sort and simulate — the answer can be obtained just by counting with conditional checks.

Example: When \(L=20, Y=5\)
- If \(A_i \ge 26\) (\(>25\)), survives even without connection
- \(21 \sim 25\) survives if connected
- \(20\) or below is impossible

Algorithm

1. Compute \(threshold = L + Y\)
2. Count the following across all smartphones:
   • survive: the number of smartphones with \(A_i > threshold\) (survive without connection)
   • need: the number of smartphones with \(L < A_i \le threshold\) (survive if connected)
3. The answer is
   $\(survive + \min(K, need)\)\( (the number that can be saved does not exceed the number of ports \)K$)

Complexity

• Time complexity: \(O(N)\) (just a single pass)
• Space complexity: \(O(1)\) (only counters, excluding the input array)

Implementation Notes

• Since “the phone powers off at exactly \(L\%\),” the survival condition uses \(>\) (strict inequality) — be careful about this.

  • Survival condition without connection: \(A_i > L + Y\)
  • Condition for being connectable (currently alive): \(A_i > L\)

• The answer is determined in a single line: survive + min(K, need).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, L, K, Y = map(int, input().split())
    A = list(map(int, input().split()))

    survive = 0
    need = 0
    threshold = L + Y

    for a in A:
        if a > threshold:
            survive += 1
        elif a > L:
            need += 1

    print(survive + min(K, need))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.