Overview

This problem asks us to raise the height of each section by the minimum required amount so that the height difference between adjacent sections is at most \(D\).

The key point is that the final height of each section is uniquely determined as the “minimum height enforced by the surrounding higher sections”.

Analysis

Let \(B_i\) be the final height of section \(i\).

From the conditions, the difference in height between adjacent sections is at most \(D\), so for any sections \(i\) and \(j\),

\[ B_i \geq B_j - D|i-j| \]

holds.

Also, since we cannot decrease the heights during the operations,

\[ B_j \geq A_j \]

must hold.

Therefore,

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

must hold for all \(j\).

In other words, the final height of section \(i\) must be at least

\[ \max_j (A_j - D|i-j|) \]

If we define this value as \(H_i\), we have

\[ H_i = \max_j (A_j - D|i-j|) \]

This represents the minimum height required for section \(i\) when we consider that “the original height \(A_j\) of each section \(j\) can decrease by at most \(D\) for every unit of distance away from it”.

For example, if there is a section with height \(10\), it imposes constraints on its neighbors: the adjacent section must be at least \(10-D\), the next one must be at least \(10-2D\), and so on.

Why this is optimal

Since all \(C_i\) are positive, raising the height more than necessary will always increase the cost.

Furthermore, raising a certain section excessively does not allow other sections to be lower; rather, it only creates additional constraints.

Therefore, it is optimal to make the height of each section as low as possible, which is \(H_i\).

Why a naive approach is too slow

For each section \(i\), if we check all sections \(j\) to calculate

\[ \max_j (A_j - D|i-j|) \]

the time complexity will be \(O(N^2)\).

Since \(N \leq 10^6\), this will easily exceed the time limit.

Therefore, we separate the influence from the left side and the influence from the right side to compute it in linear time.

Algorithm

The required height \(H_i\) for section \(i\) is the maximum of the constraints coming from the left and those coming from the right.

Constraints from the left

Let \(L_i\) be the constraint coming from the left side (i.e., sections \(j \leq i\)):

\[ L_i = \max_{j \leq i}(A_j - D(i-j)) \]

This can be calculated sequentially from left to right:

• \(L_1 = A_1\)
• For \(i \geq 2\),

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

This is because the maximum constraint from the left up to section \(i-1\), which is \(L_{i-1}\), weakens by \(D\) when moving to section \(i\).

Constraints from the right

Similarly, let \(R_i\) be the constraint coming from the right side (i.e., sections \(j \geq i\)):

\[ R_i = \max_{j \geq i}(A_j - D(j-i)) \]

This can be calculated sequentially from right to left:

• \(R_N = A_N\)
• For \(i \leq N-1\),

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

Final Heights

The final height required for section \(i\) is the maximum of the constraint from the left and the constraint from the right:

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

Then, the cost to raise section \(i\) from \(A_i\) to \(H_i\) is

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

Summing this up for all sections gives the final answer.

Concrete Example

For example, let

\[ A = [10, 0, 0, 7], \quad D = 3 \]

Looking from the left:

\[ L = [10, 7, 4, 7] \]

Each time we move to the right from the section with height \(10\), the minimum height decreases to \(7\) and then \(4\).

Looking from the right:

\[ R = [10, 1, 4, 7] \]

Therefore, the final height is:

\[ H = [10, 7, 4, 7] \]

The difference between all adjacent sections is at most \(3\), and this is the minimum required height.

Complexity

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

Implementation Details

We can store the constraints from the left, \(L_i\), in an array.

The constraints from the right, \(R_i\), do not need to be stored in an array, as we can maintain them in a variable cur while scanning from right to left.

For each section, we can find the final height by doing:

h = max(L[i], cur);

and add the cost using:

ans += 1LL * (h - A[i]) * C[i];

Since the answer can be very large, you should use long long instead of int.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, D;
    cin >> N >> D;

    vector<int> A(N), C(N), L(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    int cur = 0;
    for (int i = 0; i < N; i++) {
        if (i == 0) cur = A[i];
        else cur = max(A[i], cur - D);
        L[i] = cur;
    }

    long long ans = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (i == N - 1) cur = A[i];
        else cur = max(A[i], cur - D);

        int h = max(L[i], cur);
        ans += 1LL * (h - A[i]) * C[i];
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.