Overview

This problem asks us to minimize the final altitude when using a ropeway exactly once during a mountain climb (which sets the current altitude to \(\lfloor h / 2 \rfloor\)).

There are \(N+1\) possible timings to use the ropeway. By efficiently simulating the altitude transitions after each possible timing, we can solve the problem in \(O(N)\) total time complexity.

---

Analysis

1. Naive Approach and Its Limitations

Let’s fix the timing of ropeway usage to after the \(j\)-th segment (\(j = 0, 1, \ldots, N\)). To determine the final altitude, we follow these steps:

1. Climb normally from the beginning through the \(j\)-th segment.
2. Use the ropeway after the \(j\)-th segment, halving the altitude.
3. Climb normally from there through the \(N\)-th segment.

If we naively simulate this for each \(j\), it takes \(O(N)\) computation per timing. Since there are \(N+1\) possible timings, the total complexity becomes \(O(N^2)\), which will result in a Time Limit Exceeded (TLE) under the constraint \(N \le 5 \times 10^5\).

Therefore, we need to compute the “behavior after using the ropeway” in \(O(1)\).

2. Properties of Altitude Transitions (Rephrasing “Cannot Go Below 0”)

The altitude transition is expressed as \(h \leftarrow \max(h + D_i, 0)\). The operation of “resetting to \(0\) when it would go below \(0\)” has a very convenient property.

Consider the final value when starting from initial value \(x\) and sequentially applying changes \(D_1, D_2, \ldots, D_k\). If the value is never reset to \(0\) along the way, the result is simply \(x + \sum D_i\). However, if it is reset to \(0\) at some point, let \(m\) be the position of the last reset. After that point, it reaches the goal without being reset again, so the final value is \(\sum_{i=m+1}^k D_i\).

In fact, the final value including this “reset to \(0\) along the way” behavior equals “the maximum of the simple prefix sums starting from all candidate reset positions (including the case of no reset)”.

Concrete Example

Consider initial value \(x = 10\) with changes \([-20, +5]\). - Naive simulation: 1. Initial value: \(10\) 2. After 1st segment: \(\max(10 - 20, 0) = 0\) 3. After 2nd segment: \(\max(0 + 5, 0) = 5\) Final altitude is \(5\).

• Maximum value method:
  1. No reset (starting from initial value \(10\)): \(10 - 20 + 5 = -5\)
  2. Reset after 1st segment (starting from \(0\)): \(0 + 5 = 5\)
  3. Reset after 2nd segment (starting from \(0\)): \(0\) The maximum of these is \(\max(-5, 5, 0) = 5\), which matches the simulation result.

Using this property, if the altitude immediately after using the ropeway is \(x\), the final altitude from there to the goal can be expressed as the maximum of the following two values:

1. Case where it is never reset to \(0\): $\(x + (\text{sum of changes from segment } j+1 \text{ to } N)\)$
2. Case where it is reset to \(0\) at least once along the way: $\(\max_{m=j+1}^N (\text{sum of changes from segment } m+1 \text{ to } N)\)\( (※ When \)m=N\(, this is an empty sum equal to \)0$)

Both of these values can be obtained in \(O(1)\) for any \(j\) by precomputing “suffix sums.”

---

Algorithm

We precompute the following three arrays:

1. Array \(h\) (altitude when climbing normally from the start)

   • \(h[i]\): altitude immediately after climbing normally through segments \(1\) to \(i\).
   • Transition: \(h[i] = \max(0, h[i-1] + D_i)\) (with \(h[0] = 0\))

2. Array \(A\) (simple suffix sum)

   • \(A[i]\): sum of changes from segment \(i\) to \(N\).
   • \(A[i] = A[i+1] + D_i\) (with \(A[N+1] = 0\))

3. Array \(B\) (maximum of suffix sums)

   • \(B[i]\): maximum of “cumulative sum from some position to the goal” among positions from segment \(i\) onward.
   • \(B[i] = \max(A[i+1], B[i+1])\) (with \(B[N+1] = 0\))

Using the Ropeway After the \(j\)-th Segment

The altitude immediately after using the ropeway is \(h'_j = \lfloor h[j] / 2 \rfloor\). The final altitude can then be computed in \(O(1)\) with the following formula: $\(\text{val} = \max( h'_j + A[j+1], B[j+1] )\)$

We compute this value for all \(j = 0, 1, \ldots, N\), and the minimum among them is the answer.

---

Complexity

• Time Complexity: \(O(N)\) Computing array \(h\) (forward scan) takes \(O(N)\), computing arrays \(A, B\) (backward scan) takes \(O(N)\), and iterating over all ropeway positions \(j\) takes \(O(N)\). The overall algorithm runs in linear time.

• Space Complexity: \(O(N)\) We maintain several arrays of length \(N+2\), so the space complexity is \(O(N)\).

---

Implementation Notes

• Overflow Prevention: The altitude change \(D_i\) can be as large as \(10^9\) or as small as \(-10^9\), and cumulative sums may exceed the range of 32-bit integers. Therefore, in C++ you need to use the long long type (in Python, the standard integer type handles this automatically).

• Index Boundaries: To avoid out-of-bounds array access at boundary conditions such as \(j = 0\) (before the 1st segment) or \(j = N\) (after the \(N\)-th segment), we allocate arrays of size \(N+2\) and initialize them appropriately (A[N+1] = 0, B[N+1] = 0).

  Source Code

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

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

    vector<long long> h(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        h[i] = max(0LL, h[i - 1] + D[i]);
    }

    vector<long long> A(N + 2, 0);
    vector<long long> B(N + 2, 0);
    for (int i = N; i >= 1; --i) {
        A[i] = A[i + 1] + D[i];
        B[i] = max(A[i + 1], B[i + 1]);
    }

    long long min_val = -1;
    bool first = true;

    for (int j = 0; j <= N; ++j) {
        long long h_prime = h[j] / 2;
        long long val = max(h_prime + A[j + 1], B[j + 1]);
        if (first || val < min_val) {
            min_val = val;
            first = false;
        }
    }

    cout << min_val << "\n";

    return 0;
}

---

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