概要

部分列の最後の曲を固定した動的計画法を考えます。
遷移式に現れる \(B_j \times B_i\) を「直線の値」として扱うことで、Li Chao Tree を使って高速に最大値を求めます。

考察

曲 \(i\) を最後に選ぶ部分列の最大スコアを \(dp_i\) とします。

曲 \(i\) だけを選ぶ場合、スコアは \(A_i\) です。

一方、曲 \(j \ (j < i)\) を最後にする部分列の後ろに曲 \(i\) を追加する場合、スコアは

\(dp_j + A_i + B_j \times B_i\)

になります。

したがって、遷移は次のように書けます。

\[ dp_i = A_i + \max \left(0, \max_{j < i}(dp_j + B_j \times B_i) \right) \]

ここで \(0\) は「曲 \(i\) から新しく部分列を始める」ことを表しています。

答えは

\[ \max_i dp_i \]

です。

---

素朴に各 \(i\) についてすべての \(j < i\) を調べると、計算量は \(O(N^2)\) になります。
\(N \leq 10^5\) なので、これは間に合いません。

重要なのは、遷移の中の

\[ dp_j + B_j \times B_i \]

を、\(x = B_i\) における直線の値として見られることです。

曲 \(j\) に対して、次の直線を考えます。

\[ f_j(x) = B_j x + dp_j \]

すると、

\[ dp_j + B_j \times B_i = f_j(B_i) \]

です。

つまり、各 \(i\) について必要なのは、

• これまでの曲 \(j < i\) から作られる直線 \(f_j\)
• それらのうち \(x = B_i\) で最大値を取るもの

を高速に求めることです。

これは Li Chao Tree によって実現できます。

アルゴリズム

以下の順に曲を左から処理します。

1. これまでの曲から作られた直線集合に対して、\(x = B_i\) での最大値を問い合わせる。
2. その値を \(q\) とすると、

$\( dp_i = A_i + \max(0, q) \)$

とする。 3. 答え候補として \(dp_i\) を記録する。 4. 曲 \(i\) を今後の遷移に使うため、直線

$\( f_i(x) = B_i x + dp_i \)$

を Li Chao Tree に追加する。

---

具体的には、コードでは次のように対応しています。

q = query(b)
if q > 0:
    dp = a + q
else:
    dp = a

これは

\[ dp_i = A_i + \max(0, q) \]

を表しています。

その後、

add_line(b, dp)

によって、直線

\[ y = B_i x + dp_i \]

を追加しています。

---

Li Chao Tree について

Li Chao Tree は、直線の集合に対して

• 直線を追加する
• ある \(x\) における最大値を求める

という操作をどちらも \(O(\log N)\) 程度で行えるデータ構造です。

今回、問い合わせる \(x\) は必ずどれかの \(B_i\) です。
そのため、すべての \(B_i\) を集めてソートし、座標圧縮しています。

xs = sorted(set(B))
pos = {x: i for i, x in enumerate(xs)}

Li Chao Tree はこの xs 上でのみ値を比較します。

各直線は

\[ y = mx + c \]

の形で管理されます。

今回追加する直線では、

• 傾き \(m = B_i\)
• 切片 \(c = dp_i\)

です。

計算量

\(M\) を異なる \(B_i\) の個数とします。
\(M \leq N\) です。

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

\(M \leq N\) なので、全体として

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

です。

実装のポイント

• \(dp_i\) は大きくなる可能性があるため、十分大きな整数型を使う必要があります。

  • Python では整数が任意精度なので問題ありません。

• まだ直線が 1 本も追加されていない状態で query すると、非常に小さい値 NEG を返します。

  • その場合は q > 0 にならないため、曲 \(i\) 単独で始める処理になります。

• 直線は、必ず現在の曲の \(dp_i\) を計算した後に追加します。

  • 先に追加してしまうと、同じ曲を直前の曲として使ってしまい、\(j < i\) の条件に反します。

• \(A_i\) や \(B_i\) は負になることがあります。

  • そのため、単純な貪欲法では解けません。

  • 「以前の最良状態を直線として管理する」という DP + Li Chao Tree の形にすることが重要です。

    ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    vals = data[1:]

    A = vals[0::2]
    B = vals[1::2]

    xs = sorted(set(B))
    m = len(xs)
    pos = {x: i for i, x in enumerate(xs)}

    size = 4 * m + 5
    line_m = [None] * size
    line_c = [0] * size

    NEG = -10**30

    def add_line(nm, nc):
        node = 1
        l = 0
        r = m

        while True:
            cm = line_m[node]
            if cm is None:
                line_m[node] = nm
                line_c[node] = nc
                return

            cc = line_c[node]
            mid = (l + r) >> 1
            xmid = xs[mid]

            if nm * xmid + nc > cm * xmid + cc:
                line_m[node], nm = nm, cm
                line_c[node], nc = nc, cc
                cm = line_m[node]
                cc = line_c[node]

            if r - l == 1:
                return

            xl = xs[l]
            xr = xs[r - 1]

            if nm * xl + nc > cm * xl + cc:
                node <<= 1
                r = mid
            elif nm * xr + nc > cm * xr + cc:
                node = (node << 1) | 1
                l = mid
            else:
                return

    def query(x):
        p = pos[x]
        node = 1
        l = 0
        r = m
        res = NEG

        while True:
            cm = line_m[node]
            if cm is not None:
                v = cm * x + line_c[node]
                if v > res:
                    res = v

            if r - l == 1:
                return res

            mid = (l + r) >> 1
            if p < mid:
                node <<= 1
                r = mid
            else:
                node = (node << 1) | 1
                l = mid

    ans = NEG

    for a, b in zip(A, B):
        q = query(b)
        if q > 0:
            dp = a + q
        else:
            dp = a

        if dp > ans:
            ans = dp

        add_line(b, dp)

    print(ans)

if __name__ == "__main__":
    main()

---

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