Day 173-Q2 — 2026-10-09 | 個数×重さで課金される便分け（簡易版 LARSCH: 二分探索なしのオンライン Monge DP）

📋 コピーimport sys


def solve(n, c, s):
    INF = float('inf')
    dp = [INF] * (n + 1)
    x = [0] * (n + 1)          # x[j] = いま分かっている dp[j] の最良の直前の区切り
    dp[0] = 0

    def check(i, j):           # 区切り i から j への遷移を試す（dp[i] は確定済み）
        v = dp[i] + c + (s[j] - s[i]) * (j - i)
        if v < dp[j]:
            dp[j] = v
            x[j] = i

    # 簡易版 LARSCH: rec(l, r) を呼ぶ時点で
    #   dp[l] は確定、x[r] は区切り候補 0..l の中での最良
    def rec(l, r):
        if r - l <= 1:
            return
        m = (l + r) // 2
        for i in range(x[l], x[r] + 1):   # m の最良は x[l]..x[r] の間にある（Monge）
            check(i, m)
        rec(l, m)                          # ここで dp[m] が確定
        for i in range(l + 1, m + 1):      # r に l+1..m からの遷移を足す
            check(i, r)
        rec(m, r)

    check(0, n)
    rec(0, n)
    return dp[n]


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])
    print(solve(n, c, s))


if __name__ == "__main__":
    main()