Overview

This problem asks us to raise the height of each section of a single path collapsed by heavy rain, at minimum cost, such that the difference in height between any two adjacent sections is at most \(D\).

Since the optimal final height of each section is uniquely determined by the initial heights of all other sections, we can solve this efficiently in \(O(N)\) time complexity using cumulative maximums.

Analysis

1. Conditions on the Final Heights

The condition that the height difference between all adjacent sections is at most \(D\) is equivalent to the following relation holding for any two sections \(i, j\): $\(|A'_i - A'_j| \leq |i - j| \times D\)$

Also, since we cannot shave off the road (decrease the height), we must have \(A'_i \geq A_i\) for all \(i\).

Combining these, for the initial height \(A_j\) of any section \(j\), the final height \(A'_i\) of section \(i\) must satisfy the following condition: $\(A'_i \geq A_j - |i - j| \times D\)$

Since this inequality must hold for all \(j\) (\(1 \leq j \leq N\)), the lower bound for the final height of section \(i\) is: $\(A'_i \geq \max_{1 \leq j \leq N} (A_j - |i - j| \times D)\)$

2. Validity of the Lower Bound

If we set the final height \(A'_i\) to this “lower bound itself” for all \(i\), will all the conditions of the problem be satisfied? In fact, if we define \(A'_i = \max_{j} (A_j - |i - j| \times D)\), the following two properties hold:

1. At least the initial state: When \(j = i\), we have \(A_j - |i - j| \times D = A_i\), so \(A'_i \geq A_i\) always holds.
2. Adjacent difference is at most \(D\): From the triangle inequality \(|i - j| - 1 \leq |i + 1 - j| \leq |i - j| + 1\), the following holds for any \(j\): $\(A_j - |i + 1 - j| \times D \leq A_j - (|i - j| - 1) \times D = (A_j - |i - j| \times D) + D \leq A'_i + D\)\( By taking the maximum over all \)j\(, we obtain \)A’_{i+1} \leq A’_i + D\(. Similarly, we can show \)A’i \leq A’{i+1} + D\(, which guarantees that the difference between adjacent heights is always at most \)D$.

Since the costs \(C_i\) are all positive (\(1 \leq C_i\)), to minimize the total cost, it is optimal to make the height of each section exactly equal to this minimum required value \(A'_i\).

3. Formula Transformation for Optimization

If we naively search all \(j\) for each \(i\), it will take \(O(N^2)\) time, which will result in a Time Limit Exceeded (TLE) for \(N \le 10^6\). Therefore, we eliminate the absolute value and rearrange the expression.

• When \(j \leq i\) (to the left of or equal to \(i\)): $\(A_j - |i - j| \times D = A_j - (i - j) \times D = (A_j + j \times D) - i \times D\)$
• When \(j \geq i\) (to the right of or equal to \(i\)): $\(A_j - |i - j| \times D = A_j - (j - i) \times D = (A_j - j \times D) + i \times D\)$

By rearranging the formulas this way, we can separate the terms inside the maximum into parts depending on \(i\) and parts depending on \(j\).

Algorithm

Let’s consider 0-indexed representation (indices from \(0\) to \(N-1\)).

1. Calculate the cumulative maximum from the left: For all \(i\), calculate \(L_i = \max_{0 \leq j \leq i} (A_j + j \times D)\). This can be computed in \(O(N)\) overall by scanning from left to right and updating cur = max(cur, A[i] + i * D).

2. Calculate the cumulative maximum from the right and the cost: For all \(i\), calculate \(R_i = \max_{i \leq j \leq N-1} (A_j - j \times D)\). This can be computed in \(O(N)\) overall by scanning from right to left and updating cur = max(cur, A[i] - i * D).

3. Calculate the target height and cost: The optimal height \(A'_i\) for each section \(i\) is obtained as: $\(A'_i = \max(L_i - i \times D, R_i + i \times D)\)\( The required cost is \)(A’_i - A_i) \times C_i$. Summing this over all sections gives the final answer.

Complexity

• Time Complexity: \(O(N)\) Since we only perform one pass from the left and one pass from the right, it runs extremely fast in less than 0.1 seconds even for \(N = 10^6\).
• Space Complexity: \(O(N)\) We use \(O(N)\) memory to store the array \(L\) for the cumulative maximums from the left. (We do not need a separate array for the cumulative maximums from the right, \(R\), because we can calculate the answer on the fly while maintaining \(R\) in a single variable).

Implementation Points

• Initializing with large values: When finding the cumulative maximum, initialize the starting value (cur) with a sufficiently small value (such as -10**18).

• Fast I/O: When handling inputs of \(N = 10^6\) in Python, you can reduce I/O overhead by reading the entire input at once using sys.stdin.read.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    D = int(data[1])

    A = [int(x) for x in data[2 : 2 + N]]
    C = [int(x) for x in data[2 + N : 2 + 2 * N]]

    # L[i] = max_{j <= i} (A[j] + j * D)
    L = [0] * N
    cur = -10**18
    for i in range(N):
        val = A[i] + i * D
        if val > cur:
            cur = val
        L[i] = cur

    # R[i] = max_{j >= i} (A[j] - j * D)
    # 同時に、目標の高さ target = max(L[i] - i * D, R[i] + i * D) を求めてコストを計算する
    ans = 0
    cur = -10**18
    for i in range(N - 1, -1, -1):
        val = A[i] - i * D
        if val > cur:
            cur = val
        target = L[i] - i * D
        r_val = cur + i * D
        if r_val > target:
            target = r_val
        ans += (target - A[i]) * C[i]

    print(ans)


if __name__ == "__main__":
    solve()

---

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