Overview

This problem asks us to select one or more songs from a given set of songs while preserving their original order to maximize the total score. For each adjacent pair of selected songs, the product of their respective “compatibility values” is added as a bonus.

Analysis

Formulation using Dynamic Programming (DP)

Since we decide whether to select each song one by one from left to right, we can consider using Dynamic Programming (DP). Let \(DP[i]\) be the maximum total score of a subsequence where song \(i\) is chosen as the last song.

When selecting song \(i\), if the song chosen immediately before it is \(j\) (\(j < i\)), the transition is as follows: - When song \(i\) is the first song in the playlist: $\(DP[i] = A_i\)\( - When song \)i\( is played immediately after song \)j\(: \)\(DP[i] = DP[j] + A_i + B_j \times B_i\)$

Combining these, the transition formula is as follows: $\(DP[i] = A_i + \max \left( 0, \max_{1 \leq j < i} (B_j \times B_i + DP[j]) \right)\)$

If we calculate this transition formula directly, we need to check all \(j < i\) for each \(i\). This takes \(O(N)\) per transition, leading to an overall time complexity of \(O(N^2)\). Since \(N \leq 10^5\), this will exceed the time limit (TLE).

Optimization Idea (Li Chao Tree)

Let’s focus on the expression inside the \(\max\) of the transition formula: $\(B_j \times B_i + DP[j]\)$

Here, if we let \(x = B_i\), this expression can be viewed as a linear function \(f_j(x) = B_j \cdot x + DP[j]\) of the variable \(x\). In other words, if we define a line \(y = B_j \cdot x + DP[j]\) with slope \(B_j\) and y-intercept \(DP[j]\) for each song \(j\), the transition for song \(i\) reduces to: “Finding the maximum value of \(y\) at \(x = B_i\) among the set of lines added so far.”

To efficiently handle queries that “find the maximum (or minimum) value at a specific \(x\) among multiple lines” alongside “adding a line”, we can use a Li Chao Tree.

Algorithm

We can proceed with the following steps using a Li Chao Tree:

1. Coordinate Compression: The query values of \(x\) (compatibility values \(B_i\)) can be negative. To keep the domain managed by the Li Chao Tree compact, we perform coordinate compression beforehand by sorting and removing duplicates from all \(B_i\) values.
2. Building the Li Chao Tree: Let \(M\) be the number of unique elements after coordinate compression. We build a segment tree (Li Chao Tree) with these elements as leaves.
3. DP Transitions: For \(i = 1, 2, \ldots, N\) in order, perform the following:
   • Query the Li Chao Tree to get the maximum value \(q\) of the lines at \(x = B_i\).
   • Calculate \(DP[i] = A_i + \max(0, q)\) (if \(q \leq 0\), it is better to make song \(i\) the first song in the playlist).
   • Add the new line \(y = B_i \cdot x + DP[i]\) to the Li Chao Tree.
4. Output the Answer: The maximum score will be \(\max_{1 \leq i \leq N} DP[i]\).

Complexity

• Time Complexity: \(O(N \log N)\)
  • Coordinate compression takes \(O(N \log N)\).
  • For each \(i\), the query and line addition on the Li Chao Tree take \(O(\log N)\) time, which is proportional to the height of the tree. Repeating this \(N\) times results in an overall time complexity of \(O(N \log N)\), which is well within the time limit.
• Space Complexity: \(O(N)\)
  • We use \(O(N)\) memory to store the coordinate-compressed array and the nodes of the Li Chao Tree.

Implementation Points

• Optimization via Non-recursive Implementation: Since recursive function calls have a high overhead in Python, we can achieve significant speedups by implementing the Li Chao Tree’s line addition (add_line) and point query (query) in a non-recursive (iterative) manner using loops.

• Setting Initial Values: Initialize the lines in the tree with a line representing a sufficiently small value (\(-INF\)). This ensures that queries work correctly even before any valid lines are added.

  Source Code

import sys


def solve():
    # 入力の一括読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = [0] * N
    B = [0] * N
    idx = 1
    for i in range(N):
        A[i] = int(input_data[idx])
        B[i] = int(input_data[idx + 1])
        idx += 2

    # 座標圧縮
    X = sorted(list(set(B)))
    M = len(X)

    # Xのサイズを2のべき乗にする
    sz = 1
    while sz < M:
        sz *= 2
    if M > 0:
        last_val = X[-1]
        X.extend([last_val] * (sz - M))
    else:
        X = [0] * sz

    # 各B_iのXにおけるインデックスを高速に取得するためのマップ
    pos_map = {val: i for i, val in enumerate(X[:M])}
    pos = [pos_map[b] for b in B]

    INF = 4 * 10**18
    lines = [(0, -INF)] * (2 * sz)

    # Li Chao Tree への直線の追加 (非再帰)
    def add_line(node, l, r, L):
        while True:
            T = lines[node]
            if T[1] == -INF:
                lines[node] = L
                return

            m = (l + r) // 2

            L_a, L_b = L
            T_a, T_b = T
            fl_L = L_a * X[l] + L_b
            fl_T = T_a * X[l] + T_b
            fr_L = L_a * X[r] + L_b
            fr_T = T_a * X[r] + T_b

            l_better = fl_L > fl_T
            r_better = fr_L > fr_T

            if l_better and r_better:
                lines[node] = L
                return
            if not l_better and not r_better:
                return

            fm_L = L_a * X[m] + L_b
            fm_T = T_a * X[m] + T_b
            m_better = fm_L > fm_T

            if m_better:
                lines[node] = L
                if l_better != m_better:
                    node = 2 * node
                    r = m
                    L = T
                else:
                    node = 2 * node + 1
                    l = m + 1
                    L = T
            else:
                if l_better != m_better:
                    node = 2 * node
                    r = m
                else:
                    node = 2 * node + 1
                    l = m + 1

    # 一点クエリ (非再帰)
    def query(x_idx):
        x = X[x_idx]
        res = -INF
        node = x_idx + sz
        while node > 0:
            T = lines[node]
            if T[1] != -INF:
                val = T[0] * x + T[1]
                if val > res:
                    res = val
            node //= 2
        return res

    dp = [0] * N
    for i in range(N):
        pos_i = pos[i]
        q = query(pos_i)
        dp_val = A[i] + (q if q > 0 else 0)
        dp[i] = dp_val
        add_line(1, 0, sz - 1, (B[i], dp_val))

    print(max(dp))


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.