Overview

This problem asks for the minimum number of operations to reduce all sections’ snow to 0 or less, where each operation decreases the snow by 1cm across a contiguous range of sections. This can be reduced to a classic problem known as the “staircase painting” problem.

Analysis

Visualizing the Problem

First, let’s think of each section’s snow amount as a bar chart.

For example, when \(A = [3, 5, 2, 4]\):

    ■
    ■ 
■   ■   ■
■   ■   ■
■ ■ ■ ■
■ ■ ■ ■
■ ■ ■ ■
─────────
1 2 3 4

Key Insight

The operation “decrease a contiguous range by 1cm” corresponds to “removing one horizontal layer across a contiguous portion” in the bar chart.

In other words, this problem is equivalent to “How many horizontal lines (contiguous horizontal segments) are needed to cover the entire bar chart?”

Problem with the Naive Approach

If we naively simulate by “choosing the most efficient interval each time,” up to \(10^9\) operations may be needed, resulting in TLE.

The Key to the Solution

Looking at the bar chart from left to right: - Where the height increases, we need to add new horizontal lines - Where the height decreases or stays the same, we can simply extend (or terminate) existing horizontal lines

For example, in the above case: - Section 1: height 3 → 3 lines needed - Section 2: height 5 (+2 increase) → add 2 lines - Section 3: height 2 (decrease) → no addition needed - Section 4: height 4 (+2 increase) → add 2 lines

Total: \(3 + 2 + 0 + 2 = 7\) operations

Algorithm

The answer can be computed with the following formula:

\[\text{Answer} = A_0 + \sum_{i=1}^{N-1} \max(0, A_i - A_{i-1})\]

In other words: 1. First, add the snow amount \(A_0\) of the first section 2. For adjacent sections, if the latter section is taller, add the difference

This is equal to the sum of the positive parts of the difference array.

Verification with a Concrete Example

For \(A = [3, 5, 2, 4]\): - \(A_0 = 3\) - \(A_1 - A_0 = 5 - 3 = 2 > 0\) → add - \(A_2 - A_1 = 2 - 5 = -3 < 0\) → do not add - \(A_3 - A_2 = 4 - 2 = 2 > 0\) → add

Answer: \(3 + 2 + 0 + 2 = 7\)

Complexity

• Time complexity: \(O(N)\) (just a single pass through the array)
• Space complexity: \(O(N)\) (storing the input array)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the answer can be as large as approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but in C++ and similar languages, you need to use long long.

• It is important not to forget to add the first element \(A_0\).

  Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # この問題は「階段の塗り分け」問題と同等です
    # 各区画の雪の量を棒グラフとして考えると、
    # 1回の操作で連続する区間を1cm減らせます
    # 
    # 最小回数は、隣接する区画間で「増加した分」の合計 + 最初の区画の値
    # これは差分配列の正の部分の和に相当します
    
    # A[0] から始めて、A[i] > A[i-1] となる部分で新しい「層」が必要
    # つまり、増加分だけ追加の操作が必要
    
    result = A[0]  # 最初の区画の雪を除去するのに必要な回数
    
    for i in range(1, N):
        if A[i] > A[i-1]:
            result += A[i] - A[i-1]
    
    print(result)

solve()

---

This editorial was generated by claude4.5opus.