Overview

This problem asks you to find the total stamina consumed when climbing a staircase with \(N\) steps. Basically, the stamina consumed equals the height of each step, but when climbing a step that is higher than the immediately preceding step, the stamina consumption doubles. You need to correctly determine this condition and compute the result.

Analysis

The key point of this problem is “comparing the current step height with the previous step height”.

• Step 1: Always consumes \(A_1\) stamina.
• Step \(i\) (for \(i \ge 2\)):
  • If \(A_i > A_{i-1}\), then \(2 \times A_i\) stamina is consumed.
  • Otherwise (i.e., \(A_i \le A_{i-1}\)), then \(A_i\) stamina is consumed.

Checking the constraints, the number of steps \(N\) is at most \(2 \times 10^5\). By processing from step 1 onward, comparing each step with the previous one, we can find the answer by examining each step exactly once.

Also, since each step height \(A_i\) can be up to \(10^9\) and there are up to \(2 \times 10^5\) of them, the total value can reach approximately \(2 \times 10^9 \times 2 \times 10^5 = 4 \times 10^{14}\). This exceeds the range of a typical 32-bit integer type (approximately \(2 \times 10^9\)), so depending on the programming language, you need to use a 64-bit integer type (in Python, the standard integer type handles this automatically).

Algorithm

Perform the computation with the following steps:

1. Prepare a variable total_stamina to hold the cumulative stamina, and initialize it with the first step height \(A_1\).
2. For \(i = 2\) to \(N\), repeat the following:
   • If \(A_i > A_{i-1}\), add \(2 \times A_i\) to total_stamina.
   • Otherwise, add \(A_i\) to total_stamina.
3. Output the final value of total_stamina.

Complexity

• Time complexity: \(O(N)\)
  • For \(N\) steps, each step is processed in a single loop, so the computation is proportional to \(N\).
• Space complexity: \(O(N)\)
  • If all step heights are stored in a list (array), memory proportional to the input size is required.

Implementation Notes

• Be careful with index offsets: Arrays in most programming languages start from 0, so be careful not to mix up step \(i\) in the problem statement (1-indexed) with the array index in your code (0-indexed).

• Handling the first step: Since step 1 has no “preceding step,” you can either handle it separately outside the loop or adjust the loop’s starting position to prevent out-of-bounds access.

  Source Code

import sys

def main():
    # 入力をすべて読み込み、スペースや改行で分割してリストに格納する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Nは階段の段数
    n = int(input_data[0])
    # aは各段差の高さを格納したリスト
    # a[0]が1段目、a[1]が2段目、...、a[n-1]がn段目に対応する
    a = list(map(int, input_data[1:]))
    
    if n == 0:
        return
    
    # 最初の1段目を登る際に消耗する体力（驚くことはない）
    total_stamina = a[0]
    
    # 2段目から最後の段まで順番に計算する
    for i in range(1, n):
        # 現在の段差が直前の段差よりも真に大きい場合
        if a[i] > a[i-1]:
            # 消耗する体力は2倍になる
            total_stamina += 2 * a[i]
        else:
            # 通常の体力を消耗する
            total_stamina += a[i]
    
    # 合計の消耗体力を出力する
    print(total_stamina)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.