Overview

Given the height of each step in a staircase, we calculate the total stamina required to climb all the stairs under the rule that climbing a step higher than the previous one costs twice the stamina.

Analysis

In this problem, we can find the answer by examining each step in order.
The key point is simply “whether the current step is larger than the previous step.”
If so, the stamina required to climb that step is \(2 \times A_i\). Otherwise, it is \(A_i\).

The first step (\(A_0\)) always costs normal stamina unconditionally, so we add it to the total as the initial value.
Then, for each subsequent step from the second onward, we compare it with the previous step and decide whether to add double the value or the value as-is.

This can be implemented with a simple loop, so no complex analysis or data structures are needed.
A straightforward simulation is fast enough, even with the constraint \(N \leq 2 \times 10^5\).

For example, given the input:

3
2 5 3

• First step: 2 → total = 2
  
• Second step: 5 > 2, so add 2×5 = 10 → total = 12
  
• Third step: 3 ≦ 5, so add 3 → total = 15
  Thus, the output is 15.

Algorithm

1. Add the first step \(A_0\) to the stamina total (this always costs normal stamina).
2. For each subsequent step, compare it with the previous step:
   • If \(A_i > A_{i-1}\), add \(2 \times A_i\) to the total.
   • Otherwise, add \(A_i\) as-is.
3. After processing all steps, output the total.

Complexity

• Time complexity: \(O(N)\)
  
• Space complexity: \(O(1)\) (excluding the input array)

Implementation Notes

• Pay attention to array indices and handle the case i = 0 as a special case.

• The key point is to set the first element as the initial value of the total so that processing can begin simultaneously with reading the input.

  Source Code

N = int(input())
A = list(map(int, input().split()))

total_cost = A[0]
for i in range(1, N):
    if A[i] > A[i - 1]:
        total_cost += 2 * A[i]
    else:
        total_cost += A[i]

print(total_cost)

This editorial was generated by qwen3-coder-480b.