Overview

Process each task in order, using full power mode only for tasks that cannot be completed in energy-saving mode.
Determine whether all tasks can be completed, and if so, find the minimum number of times full power mode is used.

Analysis

Let \(H_i\) be the required processing power for task \(i\).

In energy-saving mode, you can always output processing power \(A\). Therefore,

• Tasks where \(H_i \leq A\)
  → Can be completed in energy-saving mode.
• Tasks where \(H_i > A\)
  → Cannot be completed in energy-saving mode, so full power mode must be used.

The key point here is that using full power mode reduces the remaining battery to \(\lfloor p/2 \rfloor\).
The battery level never increases, and it decreases each time full power mode is used.

Therefore, there is no benefit to using full power mode for tasks where \(H_i \leq A\).

• The number of full power mode uses increases
• The battery level decreases
• Future tasks become harder to complete

So in the optimal solution, energy-saving mode is always chosen for such tasks.

On the other hand, for tasks where \(H_i > A\), there is no choice but to use full power mode.
At that point, if the current battery level is \(p\), the task cannot be completed unless \(p \geq H_i\), making it impossible.

Therefore, by examining tasks from the beginning in order:

• If \(H_i \leq A\), do nothing
• If \(H_i > A\), full power mode is required
  • If the current battery level \(p\) is less than \(H_i\), it is impossible
  • Otherwise, increment the usage count by \(1\) and update \(p\) to \(\lfloor p/2 \rfloor\)

This simulation is sufficient.

For example, consider the case \(M=20, A=7, H=[5,10,6,8,3]\).

• \(H_1=5 \leq 7\), so use energy-saving mode
• \(H_2=10 > 7\), so use full power mode
  Current battery is \(20\), so it succeeds; after use it becomes \(10\)
• \(H_3=6 \leq 7\), so use energy-saving mode
• \(H_4=8 > 7\), so use full power mode
  Current battery is \(10\), so it succeeds; after use it becomes \(5\)
• \(H_5=3 \leq 7\), so use energy-saving mode

In this case, the minimum number of full power mode uses is \(2\).

If we naively try all possibilities of “use energy-saving mode or full power mode” for each task, there are up to \(2^N\) choices.
Since \(N \leq 3 \times 10^5\), this approach is far too slow.

However, based on the analysis above, the choice at each task is essentially uniquely determined, so the problem can be solved by a single pass from the beginning.

Algorithm

Let the current battery level be \(p\) and the number of full power mode uses be ans.

The initial state is:

• \(p = M\)
• ans = 0

For each task \(H_i\), perform the following in order:

1. If \(H_i \leq A\)
   It can be completed in energy-saving mode, so do nothing.

2. If \(H_i > A\)
   Full power mode is required.

   • If \(p < H_i\), the task cannot be completed, so output -1 and terminate.
   • Otherwise, use full power mode.
     • Increment ans by \(1\)
     • Update \(p\) to \(\lfloor p/2 \rfloor\)

If all tasks are processed successfully, output ans.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

Battery level and processing power can be up to \(10^{18}\), so 32-bit integers are insufficient.
Python’s int can handle arbitrarily large integers, so there is no issue.

Also, the battery level after using full power mode is \(\lfloor p/2 \rfloor\), which in Python can be written as p //= 2.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N, M, A = map(int, input().split())
    H = list(map(int, input().split()))

    p = M
    ans = 0

    for h in H:
        if h > A:
            if p < h:
                print(-1)
                return
            ans += 1
            p //= 2

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.