Summary

We can only increase the height of each plot.
Therefore, to satisfy the condition \(|A_i' - A_{i+1}'| \leq D\), we can find the minimum height each plot must be raised to, and pay the corresponding cost.

Analysis

Let \(H_i\) be the final height.

From the condition, the height difference between adjacent plots is at most \(D\). Thus, if the height \(H_j\) of any plot \(j\) is known, the height of plot \(i\) must be at least

\[ H_j - D|i-j| \]

Furthermore, since we cannot decrease the height,

\[ H_j \geq A_j \]

Therefore, for any plot \(i\), it is constrained by all plots \(j\) as follows:

\[ H_i \geq A_j - D|i-j| \]

Thus, the minimum required final height for plot \(i\) is

\[ H_i = \max_{1 \leq j \leq N} \left( A_j - D|i-j| \right) \]

This \(H_i\) is the minimum height that satisfies the constraints from all plots.
Since the costs \(C_i\) are all positive, there is no benefit in raising the height more than necessary.

Therefore, it is optimal to raise each plot by

\[ H_i - A_i \]

---

However, checking all \(j\) for each \(i\) would take \(O(N^2)\) time, which is too slow for \(N \leq 10^6\).

To optimize this, we can split the constraints into those coming from the left and those coming from the right.

For plot \(i\), the constraint coming from the left side (\(j \leq i\)) is

\[ \max_{j \leq i} \left( A_j - D(i-j) \right) \]

This can be computed by scanning from left to right.

Similarly, the constraint coming from the right side (\(j \geq i\)) is

\[ \max_{j \geq i} \left( A_j - D(j-i) \right) \]

which can be computed by scanning from right to left.

The final required height is the maximum of these two values.

Algorithm

First, we scan from left to right to find the minimum required height for each plot from the left side.

Let \(L_i\) be the required height from the left side:

\[ L_i = \max(A_i, L_{i-1} - D) \]

This is because the height required at plot \(i-1\) can decrease by at most \(D\) at plot \(i\), resulting in \(L_{i-1} - D\).
However, it cannot be lower than the original height \(A_i\) of plot \(i\), so we take the maximum.

Next, we scan from right to left to find the minimum required height from the right side.

Let \(R_i\) be the required height from the right side:

\[ R_i = \max(A_i, R_{i+1} - D) \]

The final required height for plot \(i\) is

\[ H_i = \max(L_i, R_i) \]

Thus, the amount to increase at plot \(i\) is

\[ H_i - A_i \]

and the cost is

\[ (H_i - A_i) \times C_i \]

Summing this over all plots gives the answer.

Complexity

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

Implementation Details

We store the required heights from the left in an array req.

cur = -10**18

for i, a in enumerate(A):
    cur -= D
    if a > cur:
        cur = a
    req[i] = cur

This computes

\[ L_i = \max(A_i, L_{i-1} - D) \]

Next, we scan from the right, computing the required height from the right side while taking the maximum with the value from the left.

cur = -10**18

for i in range(N - 1, -1, -1):
    cur -= D
    if A[i] > cur:
        cur = A[i]

    req[i] = max(req[i], cur) - A[i]

At this point, req[i] represents how much we need to increase the height of plot \(i\).

Finally, we multiply this by the given cost \(C_i\) and sum them up.

ans = 0
for x, c in zip(req, map(int, input().split())):
    ans += x * c

Since the answer can be extremely large, you need to use a 64-bit integer type in other languages. In Python, you do not need to worry about integer overflow.

Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    req = [0] * N
    cur = -10**18
    d = D

    for i, a in enumerate(A):
        cur -= d
        if a > cur:
            cur = a
        req[i] = cur

    cur = -10**18
    for i in range(N - 1, -1, -1):
        a = A[i]
        cur -= d
        if a > cur:
            cur = a
        v = req[i]
        if cur > v:
            v = cur
        req[i] = v - a

    ans = 0
    for x, c in zip(req, map(int, input().split())):
        ans += x * c

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.