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

The processing power required for the \(i\)-th task is \(H_i\).

In energy-saving mode, you can always output \(A\) processing power.
Therefore, if \(H_i \leq A\), the task can always be completed in energy-saving mode.

On the other hand, if \(H_i > A\), energy-saving mode does not provide enough processing power.
Therefore, the only way to complete this task is to use full power mode.

In other words, the choice for each task is essentially predetermined:

• \(H_i \leq A\): It is optimal to use energy-saving mode
• \(H_i > A\): You have no choice but to use full power mode

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

The reasons are as follows:

• Using full power mode reduces the battery
• The number of full power mode uses also increases
• It does not make future tasks any easier

Therefore, for tasks where \(H_i \leq A\), it is always best to choose energy-saving mode.

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

However, from the observation above, the choice is uniquely determined as follows:

• If energy-saving mode is sufficient, use energy-saving mode
• If not, use full power mode

All that remains is to check whether the current battery level is at least \(H_i\) for tasks that require full power mode.

For example, consider the case where \(M = 20, A = 5\), and the tasks are \([3, 8, 4, 9]\):

• \(3 \leq 5\), so use energy-saving mode
• \(8 > 5\), so use full power mode
  Current battery is \(20\), so execution is possible
  Battery after use is \(\lfloor 20 / 2 \rfloor = 10\)
• \(4 \leq 5\), so use energy-saving mode
• \(9 > 5\), so use full power mode
  Current battery is \(10\), so execution is possible
  Battery after use is \(\lfloor 10 / 2 \rfloor = 5\)

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

Algorithm

Manage the current battery level as battery. Its initial value is \(M\).
Also, let ans be the number of times full power mode is used.

Process tasks from the beginning in order:

1. Let \(H\) be the required processing power of the task
2. If \(H \leq A\), it can be processed in energy-saving mode, so do nothing
3. If \(H > A\), full power mode is required
   • If battery < H, this task cannot be processed, so output -1 and terminate
   • Otherwise, use full power mode
     • Increment ans by \(1\)
     • Update battery to \(\lfloor battery / 2 \rfloor\)

If all tasks are processed successfully, ans is the answer.

Complexity

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

Implementation Notes

Since \(M, A, H_i\) can be up to \(10^{18}\), you need to use long long instead of int.

Also, whether a task can be processed in full power mode should be checked using the battery value before it is reduced.

That is, the order must be:

if (battery < H) {
    cout << -1 << '\n';
    return 0;
}

ans++;
battery /= 2;

Since the input \(H_i\) values are processed in order, there is no need to store them all in an array.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long M, A;
    cin >> N >> M >> A;

    long long battery = M;
    int ans = 0;

    for (int i = 0; i < N; i++) {
        long long H;
        cin >> H;

        if (H <= A) {
            continue;
        }

        if (battery < H) {
            cout << -1 << '\n';
            return 0;
        }

        ans++;
        battery /= 2;
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.