概要

各区画の高さは増やすことしかできません。
そのため、条件 \(|A_i' - A_{i+1}'| \leq D\) を満たすために、各区画を最低限どこまで高くする必要があるかを求め、その分だけコストを払えばよいです。

考察

最終的な高さを \(H_i\) とします。

条件より、隣接する区画の高さ差は最大 \(D\) なので、任意の区画 \(j\) の高さ \(H_j\) が分かっているとき、区画 \(i\) の高さは少なくとも

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

以上でなければなりません。

また、操作では高さを下げられないので、

\[ H_j \geq A_j \]

です。

したがって、任意の区画 \(i\) について、すべての区画 \(j\) から次の制約を受けます。

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

よって、区画 \(i\) の最終的な高さとして必要な最小値は

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

です。

この \(H_i\) は、すべての区画からの制約を満たす最小の高さです。
コスト \(C_i\) はすべて正なので、必要以上に高さを上げても得をすることはありません。

したがって、各区画を

\[ H_i - A_i \]

だけ上げるのが最適です。

---

ただし、各 \(i\) についてすべての \(j\) を調べると \(O(N^2)\) になり、\(N \leq 10^6\) では間に合いません。

そこで、左から来る制約と右から来る制約に分けて考えます。

区画 \(i\) に対して、左側 \(j \leq i\) から来る制約は

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

です。

これは左から順に見ていくことで求められます。

同様に、右側 \(j \geq i\) から来る制約は

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

で、これは右から順に見ていくことで求められます。

最終的に必要な高さは、この 2 つの最大値です。

アルゴリズム

まず、左から順に見て、各区画に対して左側から要求される最低高さを求めます。

左側からの必要高さを \(L_i\) とすると、

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

です。

なぜなら、区画 \(i-1\) で必要だった高さは、区画 \(i\) では最大で \(D\) だけ低くてもよいので、\(L_{i-1} - D\) になります。
ただし、区画 \(i\) 自身の元の高さ \(A_i\) より低くすることはできないので、最大を取ります。

次に、右から順に見て、右側から要求される最低高さを求めます。

右側からの必要高さを \(R_i\) とすると、

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

です。

区画 \(i\) の最終的に必要な高さは

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

です。

したがって、区画 \(i\) で増やす量は

\[ H_i - A_i \]

であり、コストは

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

です。

これをすべての区画について合計すれば答えになります。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

左からの必要高さを配列 req に保存します。

cur = -10**18

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

これは

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

を計算しています。

次に右から見て、右側からの必要高さを計算しながら、左側の値と最大を取ります。

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]

この時点で req[i] は、区画 \(i\) を何だけ高くする必要があるかを表します。

最後に、入力されたコスト \(C_i\) と掛け合わせて合計します。

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

答えは最大で非常に大きくなる可能性があるため、他の言語では 64 bit 整数型を使う必要があります。Python では整数の桁あふれを気にする必要はありません。

ソースコード

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()

---

この解説は gpt-5.5-high によって生成されました。