Overview

This problem asks for the minimum number of operations (incrementing element values) required to eliminate all valleys (positions \(i\) where \(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)) in a sequence \(H\) of \(N\) elements.

Analysis

To eliminate a valley at index \(i\), we must do one of the following: 1. Increase \(H_i\). 2. Decrease \(H_{i-1}\). 3. Decrease \(H_{i+1}\).

However, the allowed operation only lets us increase heights. Therefore, to eliminate a valley, we must increase the height of the middle element \(H_i\).

Let’s consider how much we need to increase \(H_i\) to eliminate the valley. To make it no longer a valley, at least one of the following must hold: - \(H_{i-1} \le H_i\) - \(H_i \ge H_{i+1}\)

To minimize the number of operations, we want to minimize the amount by which we increase \(H_i\). Thus, the target height should be the smaller of \(H_{i-1}\) and \(H_{i+1}\), which is \(\min(H_{i-1}, H_{i+1})\).

Here, a concern might arise: if we fix (increase the height of) index \(i\), could the already processed left neighbor \(i-1\) newly become a valley? However, we do not need to worry about this. When fixing index \(i\), we increase its height to \(\min(H_{i-1}, H_{i+1})\). At this point, the updated height of \(H_i\) will be at most \(H_{i-1}\) (\(H_i \le H_{i-1}\)). For \(H_{i-1}\) to become a valley, we would need \(H_{i-1} < H_i\). Since \(H_{i-1} \ge H_i\) is maintained even after the update, the left neighbor \(i-1\) will absolutely never become a new valley.

Therefore, a greedy approach, where we scan from left to right, find valleys, and fix them to the minimum required height on the fly, works correctly.

Algorithm

1. Initialize a variable ans (to store the answer) to \(0\).
2. Iterate through the index \(i\) from \(1\) to \(N-2\) (assuming 0-indexed; this corresponds to the \(2\)nd to \((N-1)\)-th elements in the problem description).
3. If \(H_{i-1} > H_i\) and \(H_i < H_{i+1}\) (the condition for a valley) is satisfied:
   • Set the target height target to \(\min(H_{i-1}, H_{i+1})\).
   • Add the required number of operations target - H[i] to ans.
   • Update the value of \(H_i\) to target.
4. After the loop ends, output ans.

Complexity

• Time Complexity: \(O(N)\) Since we only scan the sequence once from left to right, the processing completes in linear time relative to the number of elements \(N\). With \(N \le 10^6\), this easily fits within the time limit.
• Space Complexity: \(O(N)\) We only use memory for the array (std::vector) to store the input sequence \(H\).

Implementation Details

• Handling Overflow: The height \(H_i\) of each element can be up to \(10^9\), so the total number of operations (the answer) can reach up to around \(10^9 \times N\). This can easily exceed the maximum value of a 32-bit signed integer (int, which is approximately \(2 \times 10^9\)). Therefore, the variable ans for storing the answer and the array H for storing the elements must use a 64-bit integer type (long long in C++).

• Fast I/O: Since \(N\) can be as large as \(10^6\), untieing the synchronization of C++’s std::cin and std::cout to speed up input/output will significantly reduce the execution time.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    long long ans = 0;
    for (int i = 1; i < N - 1; ++i) {
        if (H[i - 1] > H[i] && H[i] < H[i + 1]) {
            long long target = min(H[i - 1], H[i + 1]);
            ans += target - H[i];
            H[i] = target;
        }
    }

    cout << ans << "\n";

    return 0;
}

This editorial was generated by gemini-3.5-flash-high.