Overview

This problem asks you to calculate the total stamina consumed when climbing stairs, under the condition that stamina consumption doubles when the current step height is greater than the previous step height.

Analysis

The key observations for this problem are:

1. The 1st step is a special case: Since there is no “previous step height” for the first step, it always consumes the normal stamina \(A_1\).

2. Checking from the 2nd step onward: When climbing step \(i\) (where \(i \geq 2\)), if \(A_i > A_{i-1}\), the stamina consumption doubles.

Concrete Example

For example, with \(N = 4\) and \(A = [3, 5, 2, 4]\):

Step	Height	Previous Height	Condition	Stamina Consumed
1st	3	None	Not surprised	3
2nd	5	3	\(5 > 3\) → Surprised	\(5 \times 2 = 10\)
3rd	2	5	\(2 \leq 5\) → Not surprised	2
4th	4	2	\(4 > 2\) → Surprised	\(4 \times 2 = 8\)

Total: \(3 + 10 + 2 + 8 = 23\)

Approach Considerations

This problem can be solved by simply examining each step in order. Even when \(N\) is at most \(2 \times 10^5\), since we can process everything in a single loop, a straightforward approach runs fast enough. No special techniques are required.

Algorithm

1. Add the stamina consumption for the first step \(A_0\) to the total
2. For each step from the 2nd to the \(N\)-th, repeat the following:
   • If the current step height \(A_i\) is greater than the previous step height \(A_{i-1}\), add \(2 \times A_i\)
   • Otherwise, add \(A_i\)
3. Output the total

total = A[0]
for i = 1 to N-1:
    if A[i] > A[i-1]:
        total += 2 * A[i]
    else:
        total += A[i]

Complexity

• Time complexity: \(O(N)\)
  • Only one pass through the array
• Space complexity: \(O(N)\)
  • For storing the input array \(A\)

Implementation Notes

• Be careful with indices: Since arrays are 0-indexed, “step 1” corresponds to A[0], and “step \(i\)” corresponds to A[i-1]. In the code, we process everything using 0-indexed notation.
• Watch out for overflow: Since \(A_i\) can be at most \(10^9\) and \(N\) can be at most \(2 \times 10^5\), the total can reach approximately \(4 \times 10^{14}\) in the worst case. In Python, there’s no need to worry about integer overflow, but in C++ and similar languages, you need to use long long type.
• Loop starting position: Since the 1st step always has normal consumption, processing it first and then starting the loop from the 2nd step (index 1) makes the code simpler.

Source Code

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

total = A[0]  # The first step is not surprising

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

print(total)

---

This editorial was generated by claude4.5opus.