Overview

A problem where you need to find the minimum number of operations to remove all snow, using an operation that can simultaneously reduce snow across a contiguous interval.

Analysis

In this problem, a single operation can reduce snow by 1cm across a contiguous interval, so rather than simply summing the amount of snow in each section, we need to carefully plan “which range to operate on and how many times.”

For example, consider the following input:

\[ N = 5,\quad A = [1, 2, 3, 2, 1] \]

A naive approach might suggest that we need as many operations as each \(A_i\) value, but in fact, by performing operations on contiguous intervals, we can process things efficiently.

The key insight here is to focus on the “increases.” That is, we consider the difference between adjacent elements \(A_i - A_{i-1}\). This can be interpreted as the number of new operations needed when processing from left to right.

Specifically, when looking at the array \(A\) from the beginning, if the snow height increases at some point, we need that many new operations for the increase. Conversely, if it decreases, the already chosen interval operations can potentially cover it.

Therefore, we consider the following difference array:

• \(diff[0] = A[0]\)
• \(diff[i] = A[i] - A[i-1]\ (1 \leq i < N)\)
• \(diff[N] = -A[N-1]\) (to account for dropping to 0 at the end)

The sum of positive \(diff[i]\) values gives the minimum number of operations required. This is because a positive increase means we need to start that many new “layers” of snow removal.

For example, computing the differences for the above example:

• \(diff = [1, 1, 1, -1, -1, -1]\)

The sum of positive elements is \(1 + 1 + 1 = 3\), which is the answer.

With this method, instead of operating on each element individually, we can efficiently determine the number of operations by focusing on the overall “mountain shape.”

Algorithm

1. Compute the differences between adjacent elements from the input array \(A\).
2. Set the first element \(A[0]\) as the first element of the difference array.
3. For each \(i = 1\) to \(N-1\), compute \(diff[i] = A[i] - A[i-1]\).
4. Append \(diff[N] = -A[N-1]\) at the end to account for the termination.
5. Sum up only the positive values among the differences. This is the desired minimum number of operations.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Don’t forget to append \(-A[N-1]\) at the end of the difference array.

• Using max(0, d) when summing only positive differences makes the code concise.

• Reading input efficiently handles large constraints (use sys.stdin.read).

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:]))

    # 差分を計算する（A[-1] = 0 として扱う）
    diff = [A[0]]
    for i in range(1, N):
        diff.append(A[i] - A[i-1])
    
    # 最後に0を追加して終端を考慮
    diff.append(-A[-1])

    # 正の差分の合計が答え
    ans = sum(max(0, d) for d in diff)
    print(ans)

if __name__ == "__main__":
    main()

---

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