Day 170-Q2 — 2026-10-05 | 3 乗コストの便分け（オンライン Monge DP。自分の dp 値を使う 1D/1D 漸化式を、決定単調性＋二分探索の候補キューで O(N log N)）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, c = int(data[0]), int(data[1])
    S = [0] * (n + 1)
    for i in range(n):
        S[i + 1] = S[i] + int(data[2 + i])
    dp = [0] * (n + 1)

    def val(i, j):
        # 区間 (i, j] を 1 つの便にしたときの、j までの合計コスト
        w = S[j] - S[i]
        return dp[i] + c + w * w * w

    # cand[k] は候補 i、beg[k] はその候補が最良になる最初の j（beg は増加列）
    cand = [0]
    beg = [1]
    head = 0
    for j in range(1, n + 1):
        while head + 1 < len(cand) and beg[head + 1] <= j:
            head += 1
        dp[j] = val(cand[head], j)
        if j == n:
            break
        # 新しい候補 i=j を末尾に入れる。末尾の候補より beg で既に良いなら丸ごと消す
        while len(cand) > head + 1 and val(j, beg[-1]) <= val(cand[-1], beg[-1]):
            cand.pop(); beg.pop()
        last = cand[-1]
        lo = max(beg[-1], j + 1)
        hi = n + 1                      # [lo, hi) で「j が last 以下」になる最初の位置を探す
        while lo < hi:
            mid = (lo + hi) // 2
            if val(j, mid) <= val(last, mid):
                hi = mid
            else:
                lo = mid + 1
        if lo <= n:
            cand.append(j); beg.append(lo)
    print(dp[n])


main()