Overview

This problem asks for the minimum cost required to make the height difference between adjacent sections at most \(D\), under the condition that we can only increase the height of each section.

Observation

The cost \(C_i\) to increase the height of each section \(i\) by \(1\) is always positive. Therefore, the larger the final height \(A_i'\) of each section is, the monotonically larger the cost becomes.

From this, we can see that the minimum cost is achieved by “the smallest possible height for each section among all final heights that satisfy all conditions”. In other words, we need to find the tuple of integers \((A_1', A_2', \ldots, A_N')\) satisfying \(A_i' \geq A_i\) and \(|A_i' - A_{i+1}'| \leq D\) such that each \(A_i'\) is minimized (pointwise minimum).

This “pointwise minimum” can be efficiently computed by two passes: from left to right, and from right to left.

Algorithm

1. Left-to-Right Pass: Determine the heights to satisfy the constraints from the left neighbor.

   • The height of the first section must be at least \(A_1\).
   • The height of the \(i\)-th section must be at least \(A_i\), and also at least the height of the left neighbor \(P_{i-1}\) minus \(D\) (since \(P_{i-1} \leq P_i + D \Leftrightarrow P_i \geq P_{i-1} - D\)).
   • Therefore, we update the heights as \(P_i = \max(A_i, P_{i-1} - D)\).

2. Right-to-Left Pass: Adjust the heights to satisfy the constraints from the right neighbor.

   • The height of the last section must be at least \(A_N\).
   • The height of the \(i\)-th section must be at least the current \(P_i\), and also at least the height of the right neighbor \(P_{i+1}\) minus \(D\) (since \(P_{i+1} \leq P_i + D \Leftrightarrow P_i \geq P_{i+1} - D\)).
   • Therefore, we update the heights as \(P_i = \max(P_i, P_{i+1} - D)\). At the same time, we keep the lower bound by checking against \(A_i\).

3. Cost Calculation: Calculate the total cost \(\sum_{i=1}^{N} C_i \times (P_i - A_i)\) using the final minimized heights \(P_i\).

Complexity

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

Implementation Notes

• Since \(N \leq 10^6\), the maximum increase in height can be up to \(10^5 \times 10^6 = 10^{11}\), and \(C_i\) can be up to \(10^7\), the total cost can be on the order of \(10^{18}\). Therefore, you must use a 64-bit integer type such as long long for the variable that stores the total cost.

• The left-to-right and right-to-left passes can be implemented concisely by preparing a single array P and updating it in-place.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;
    
    vector<long long> A(N), C(N), P(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }
    
    // Left-to-right pass
    long long cur = A[0];
    for (int i = 0; i < N; ++i) {
        if (A[i] > cur) cur = A[i];
        P[i] = cur;
        cur -= D;
    }
    
    // Right-to-left pass
    cur = A[N - 1];
    long long ans = 0;
    for (int i = N - 1; i >= 0; --i) {
        if (A[i] > cur) cur = A[i];
        if (cur > P[i]) P[i] = cur;
        ans += C[i] * (P[i] - A[i]);
        cur -= D;
    }
    
    cout << ans << "\n";
    return 0;
}

This editorial was generated by or-glm5.2-high.