Summary

This is a problem of finding the minimum cost to make the absolute difference between adjacent section heights at most \(D\) by performing operations to increase (and not decrease) the height of each section. We can solve this by finding the “minimum height” each section must ultimately reach, and then summing the costs to raise them to those heights.

Analysis

Important Observation: There is a lower bound for each section indicating “it must be at least this height in the end.”

First, since heights cannot be decreased, the final height \(A_i'\) must satisfy \(A_i' \geq A_i\).

Furthermore, from the constraint that the difference between adjacent sections is at most \(D\), if a section \(j\) has a height of \(A_j\), then any section \(i\) at a distance of \(|i-j|\) from it must satisfy:

\[A_i' \geq A_j - D \cdot |i-j|\]

(since the height can decrease by at most \(D\) for each step to the side).

Since this must hold for all \(j\), the lower bound for the height of section \(i\) is:

\[h_i = \max_{1 \leq j \leq N} \bigl(A_j - D \cdot |i-j|\bigr)\]

(Since the term for \(j=i\) is \(A_i\), this naturally satisfies \(h_i \geq A_i\) as well).

This lower bound \(h_i\) itself is a feasible solution

In fact, if we set the final heights to exactly \(h_i\), the adjacent sections will satisfy \(|h_i - h_{i+1}| \leq D\) (since each term \(A_j - D|i-j|\) changes by at most \(D\) between adjacent indices, their maximum value behaves the same way).

In other words, \(h_i\) is the coordinate-wise minimum solution that simultaneously achieves the “minimum height satisfying all constraints” for each section. Since any feasible solution must satisfy \(A_i' \geq h_i\), and the cost \(C_i > 0\) is positive, setting the height of every section to exactly \(h_i\) yields the minimum cost.

Therefore, the answer is:

\[\sum_{i=1}^{N} C_i \cdot (h_i - A_i)\]

Problems with the Naive Approach

Calculating \(h_i\) by checking all \(j\) for each \(i\) according to the definition takes \(O(N^2)\) time, which is too slow for \(N \leq 10^6\). We need a more efficient way.

Algorithm

We can compute \(h_i = \max_j (A_j - D|i-j|)\) by splitting the absolute value into left and right parts, using two passes (forward and backward scans).

• Contribution from the left (\(j \leq i\)): The maximum value of \(A_j - D(i-j)\) can be computed sequentially from left to right using the recurrence relation: $\(L_i = \max(A_i,\ L_{i-1} - D)\)\( This is because as we move one step to the right, all previous candidates decrease by \)D$.

• Contribution from the right (\(j \geq i\)): Similarly, we can compute the contribution from the right: $\(R_i = \max(A_i,\ R_{i+1} - D)\)$ sequentially from right to left.

• Finally, by setting \(h_i = \max(L_i, R_i)\), we can find the lower bound for all sections in \(O(N)\) time.

In the implementation, we can achieve this in two passes: first, we store \(L_i\) in h[i] during the forward scan, and then during the backward scan, we compute \(R_i\) and update h[i] to be the maximum of h[i] and \(R_i\).

Concrete Example: For \(A = [5, 0, 0, 3]\) and \(D = 2\):

• Forward scan: \(L = [5, 3, 1, 3]\)
• Backward scan: \(R = [5, 1, 3, 3]\)
• \(h = \max(L, R) = [5, 3, 3, 3]\)

For instance, for section 2, even if we decrease the height from section 1’s height of \(5\) by \(D=2\) as much as possible, it can only go down to \(3\), so \(h_2 = 3\). The cost to increase the heights is calculated as \(\sum C_i(h_i - A_i)\).

Complexity

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

Implementation Points

• Since \(A_i, C_i\) and \(N\) can be large, the answer can exceed the range of a 32-bit integer. In Python, integers automatically have arbitrary precision, so it is not an issue, but in languages like C++, you must use long long.

• Since \(N = 10^6\) is large, fast I/O using sys.stdin.buffer.read() is recommended in Python to speed up the execution.

• By storing the forward scan values in h and updating them in-place with max during the backward scan, we can complete the calculation in two passes without allocating extra arrays.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    D = int(data[idx]); idx += 1
    A = [int(x) for x in data[idx:idx+N]]; idx += N
    C = [int(x) for x in data[idx:idx+N]]; idx += N

    # h_i = max_j (A_j - D*|i-j|)  via forward and backward passes
    h = A[:]

    # forward pass
    prev = A[0]
    for i in range(1, N):
        v = prev - D
        ai = A[i]
        cur = ai if ai > v else v
        h[i] = cur
        prev = cur

    # backward pass, combine with h (take max)
    prev = A[N-1]
    # last element: forward value already A[N-1] effectively, but ensure
    if A[N-1] > h[N-1]:
        h[N-1] = A[N-1]
    for i in range(N-2, -1, -1):
        v = prev - D
        ai = A[i]
        b = ai if ai > v else v
        prev = b
        if b > h[i]:
            h[i] = b

    ans = 0
    for i in range(N):
        ans += C[i] * (h[i] - A[i])
    sys.stdout.write(str(ans) + "\n")

main()

---

This editorial was generated by claude4.8opus-high.