Overview

This problem involves processing \(N\) tasks in order while managing a laptop’s battery consumption. By leveraging the property that the battery level is halved each time full-power mode is used, we apply dynamic programming (DP) to find the minimum number of times full-power mode must be used.

Analysis

Key Insight: Upper Bound on the Number of Full-Power Mode Uses

The initial battery level \(M\) can be very large, up to \(10^{18}\), but each time full-power mode is used, the battery level is halved to \(\lfloor p/2 \rfloor\).

If we keep dividing \(10^{18}\) by 2, the battery level reaches 0 in about 60 divisions. Therefore, full-power mode can be used at most about 60 times (precisely, at most \(\log_2 M + 1\) times). This property of having a “very small number of states” is the biggest key to solving this problem.

Why a Greedy Approach Doesn’t Work

A simple greedy approach such as “use full-power mode only when the required processing power \(H_i\) exceeds \(A\)” does not work. This is because even when the current task can be cleared in energy-saving mode (\(H_i \le A\)), there are cases where we need to decide to deliberately use full-power mode now (or conserve battery) in preparation for more demanding tasks in the future.

Since the optimal timing for using full-power depends on the required processing power of future tasks, we need to explore all possibilities.

DP (Dynamic Programming) Approach

Let \(L\) (\(\approx 60\)) be the maximum number of times full-power mode can be used. We consider a DP that processes tasks from the first one onward while managing the following information:

• dp[k]: Whether it is possible to reach a state where full-power mode has been used exactly \(k\) times so far (true / false)

We update this dp array as we proceed through each task. Since the number of states is very small at \(L \le 60\), this runs efficiently even for \(N\) tasks.

Algorithm

1. Preprocessing

Create an array \(P\) representing the remaining battery level after using full-power mode \(k\) times. - Start with P[0] = M, and repeatedly append values while doing curr /= 2 as long as curr > 0. - Let the size of the array be \(L + 1\) (where \(P[L] = 0\)).

2. DP Transitions

For each task \(i = 0, 1, \ldots, N-1\), we transition from the current dp to the state next_dp after completing the task. When dp[k] is true (reachable), we have the following 2 options:

1. Use energy-saving mode

   • If the task’s required processing power is at most \(A\) (\(H_i \le A\)), the task can be cleared without consuming battery.
   • In this case, the number of full-power uses remains \(k\), so we set next_dp[k] = true.

2. Use full-power mode

   • If there is still battery remaining (\(k < L\)) and the current battery level \(P[k]\) is at least \(H_i\) (\(P[k] \ge H_i\)), the task can be cleared in full-power mode.
   • In this case, the number of full-power uses becomes \(k+1\), so we set next_dp[k+1] = true.

After processing each task, we update dp with next_dp.

3. Output the Answer

After all tasks have been processed, the answer is the minimum \(k\) (\(0 \le k \le L\)) for which dp[k] is true. If dp[k] is false for all \(k\), it is impossible to complete all tasks, so output -1.

Complexity

• Time Complexity: \(O(N \log M)\)

  • The number of times \(L\) until the battery reaches 0 is proportional to \(\log_2 M\) (when \(M \le 10^{18}\), \(L \le 60\)).
  • For each task, we iterate through a loop of size \(L\) to perform transitions, so the overall complexity is \(O(N \log M)\).
  • When \(N = 3 \times 10^5\), the total number of loop iterations is at most about \(1.8 \times 10^7\), which comfortably fits within the time limit.

• Space Complexity: \(O(N + \log M)\)

  • Storing the input task array \(H\) uses \(O(N)\) memory.
  • For the DP table, we only need to maintain 2 generations (the current state and the next state) of size \(L \approx 60\), so the space required for DP is \(O(\log M)\).

Implementation Notes

• Data Types: Since battery level \(M\) and required processing power \(H_i\) can reach up to \(10^{18}\), in C++ it is necessary to use 64-bit integer types (long long).

• Memory Optimization: When transitioning the DP table, using std::move to assign next_dp to dp avoids unnecessary memory copies and improves performance.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M, A;
    if (!(cin >> N >> M >> A)) return 0;

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

    // P[k] はフルパワーモードを k 回使った後のバッテリー残量
    vector<long long> P;
    long long curr = M;
    P.push_back(curr);
    while (curr > 0) {
        curr /= 2;
        P.push_back(curr);
    }
    int L = P.size() - 1; // P[L] = 0 となる

    // dp[k] : 現在、フルパワーモードを k 回使った状態に到達可能か (0: 不可能, 1: 可能)
    vector<char> dp(L + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < N; ++i) {
        vector<char> next_dp(L + 1, 0);
        long long hi = H[i];
        for (int k = 0; k <= L; ++k) {
            if (!dp[k]) continue;
            // 省エネモードを使用する場合
            if (hi <= A) {
                next_dp[k] = 1;
            }
            // フルパワーモードを使用する場合
            if (k < L && P[k] >= hi) {
                next_dp[k + 1] = 1;
            }
        }
        dp = move(next_dp);
    }

    int ans = -1;
    for (int k = 0; k <= L; ++k) {
        if (dp[k]) {
            ans = k;
            break;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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