Overview

This problem asks us to find the minimum cost to raise the road level of each section so that the difference in road height between any adjacent sections is at most \(D\). It is optimal to raise each section to the “minimum required height to satisfy the conditions.” This can be solved in linear time \(O(N)\) by considering the cumulative constraints from both the left and right sides.

Observations

1. Reformulating the Problem

Let \(A'_i\) be the final height of each section \(i\). The conditions that must be satisfied are as follows: - For any \(i\), \(A'_i \geq A_i\) (the road height cannot be lowered). - For any \(i\), \(|A'_i - A'_{i+1}| \leq D\).

Furthermore, since the cost \(C_i\) to raise each section by \(1\) is always positive (\(C_i \geq 1\)), to minimize the cost, we need to make each \(A'_i\) as small as possible within the range that satisfies the conditions.

2. What the Adjacency Condition Implies

The condition \(|A'_i - A'_{i+1}| \leq D\) can be rewritten as follows: - \(A'_i \geq A'_{i+1} - D\) - \(A'_{i+1} \geq A'_i - D\)

Extending this idea, for any two sections \(i\) and \(j\), the following must hold: $\(A'_i \geq A'_j - |i - j| \times D\)\( In other words, if a section \)j\( has a height of \)A’_j\(, the lower bound of the height decreases by \)D\( for every step we move away from it. Therefore, the final height \)A’_i\( of section \)i\( must be at least **the maximum of the lower bound constraints imposed by all sections \)j\(**, which is: \)\(A'_i = \max_{1 \leq j \leq N} (A_j - |i - j| \times D)\)$ To minimize the cost, it is optimal to set the height exactly to this lower bound.

3. Optimization Approach (Avoiding Naive Computation)

Trying to calculate the above maximum for all pairs of \((i, j)\) would result in a time complexity of \(O(N^2)\), which will exceed the time limit (TLE) for \(N \leq 10^6\).

To optimize this, we can separate the constraints coming from the sections to the “left” of \(i\) and those coming from the “right” of \(i\).

• Constraint from the left, \(L[i]\): The minimum required height for section \(i\) when considering only the initial heights of the sections to the left of \(i\) (from \(1\) to \(i\)).
• Constraint from the right, \(R[i]\): The minimum required height for section \(i\) when considering only the initial heights of the sections to the right of \(i\) (from \(i\) to \(N\)).

Similar to dynamic programming (DP), these can be computed using previous results in a single pass from left to right and right to left, respectively, in \(O(N)\) time.

Concrete Example

Let \(N = 3, D = 10\), and the initial heights be \(A = [10, 50, 20]\).

1. Propagation from the left, \(L\)

   • \(L[0] = A[0] = 10\)
   • \(L[1] = \max(A[1], L[0] - D) = \max(50, 10 - 10) = 50\)
   • \(L[2] = \max(A[2], L[1] - D) = \max(20, 50 - 10) = 40\)
   • \(L = [10, 50, 40]\)

2. Propagation from the right, \(R\)

   • \(R[2] = A[2] = 20\)
   • \(R[1] = \max(A[1], R[2] - D) = \max(50, 20 - 10) = 50\)
   • \(R[0] = \max(A[0], R[1] - D) = \max(10, 50 - 10) = 40\)
   • \(R = [40, 50, 20]\)

The final target height \(target\_height[i]\) should be the stricter (larger) of the two constraints from the left and right, which is \(\max(L[i], R[i])\). - \(target\_height = [\max(10, 40), \max(50, 50), \max(40, 20)] = [40, 50, 40]\)

With these heights, all adjacent differences are at most \(10\) (which is \(\leq D\)), satisfying the condition.

Algorithm

1. Constructing array \(L\) (Left-to-Right Pass)

   • Set \(L[0] = A[0]\).
   • For \(i = 1\) to \(N-1\), sequentially compute \(L[i] = \max(A[i], L[i-1] - D)\).

2. Constructing array \(R\) (Right-to-Left Pass)

   • Set \(R[N-1] = A[N-1]\).
   • For \(i = N-2\) down to \(0\) in reverse order, sequentially compute \(R[i] = \max(A[i], R[i+1] - D)\).

3. Calculating the Minimum Cost

   • For each section \(i\), the final height is \(target\_height = \max(L[i], R[i])\).
   • The height to be raised is \(target\_height - A[i]\), and the sum of this height multiplied by the cost \(C[i]\) over all sections will be the answer.

Complexity

• Time Complexity: \(O(N)\) Since we only perform a total of three passes—the left-to-right loop, the right-to-left loop, and the final cost calculation loop—the overall process completes in \(O(N)\) time complexity. This runs very quickly even for \(N = 10^6\).

• Space Complexity: \(O(N)\) Since we store the arrays \(A, C, L,\) and \(R\) of size \(N\), the space complexity is \(O(N)\).

Implementation Points

• Preventing Overflow: The cost \(C_i\), the amount of height raised, and the final total cost can be very large. In C++, you should use long long instead of int to prevent overflow during calculations.

• Fast I/O: Since the number of inputs can be as large as \(N = 10^6\), it is highly recommended in C++ to speed up standard input/output using ios_base::sync_with_stdio(false); cin.tie(NULL);.

  Source Code

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

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    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);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    vector<long long> C(N);
    for (int i = 0; i < N; ++i) {
        cin >> C[i];
    }
    
    // Left-to-right propagation
    vector<long long> L(N);
    L[0] = A[0];
    for (int i = 1; i < N; ++i) {
        L[i] = max(A[i], L[i-1] - D);
    }
    
    // Right-to-left propagation
    vector<long long> R(N);
    R[N-1] = A[N-1];
    for (int i = N - 2; i >= 0; --i) {
        R[i] = max(A[i], R[i+1] - D);
    }
    
    // Calculate the minimum total cost
    long long total_cost = 0;
    for (int i = 0; i < N; ++i) {
        long long target_height = max(L[i], R[i]);
        total_cost += (target_height - A[i]) * C[i];
    }
    
    cout << total_cost << "\n";
    
    return 0;
}

---

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