Overview

This problem asks us to select some songs from \(N\) given songs while preserving their original order, and maximize the “total score” when the product of the compatibility values of adjacent songs is added as a bonus.

By using Dynamic Programming (DP) and a Li Chao Tree (a type of Convex Hull Trick) as a data structure to optimize it, we can solve this problem quickly within the time limit.

---

Observation

1. Naive Dynamic Programming (DP)

First, let’s consider a naive dynamic programming approach. We define the DP table as follows:

• \(DP[i]\): The maximum total score of a subsequence where the last selected song is \(i\).

When selecting song \(i\), suppose we selected song \(j\) (where \(j < i\)) as the “previous song”. In this case, the total score will be \(DP[j]\) plus the “individual score of song \(i\), \(A_i\)” and the “compatibility bonus \(B_j \times B_i\)”. Also, if we select song \(i\) as the first song of the playlist, the score is simply \(A_i\).

Summarizing these, the transition equation is as follows:

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

(* The reason we use \(\max(0, \dots)\) is to treat the case where song \(i\) is the first song (i.e., no song is selected before it) as \(0\).)

If we implement this DP directly, we need to search all \(j < i\) for each \(i\), resulting in a time complexity of \(O(N^2)\). Since \(N \leq 10^5\), this will exceed the time limit (TLE).

2. Optimization Idea (Reduction to Maximum of Lines)

Let’s focus on the part of the transition equation that we want to maximize, which depends on \(j\):

\[DP[j] + B_j \times B_i\]

Here, if we let the variable \(x = B_i\), we can view this expression as a linear function (line) with respect to \(x\) as follows:

\[y = a \cdot x + b \quad (\text{where } a = B_j, \ b = DP[j])\]

In other words, the DP transition can be rephrased as follows: * For each \(j\), add a line \(y = B_j \cdot x + DP[j]\) with slope \(a = B_j\) and y-intercept \(b = DP[j]\). * In the \(i\)-th transition, find the maximum value of \(y\) at \(x = B_i\) among the set of lines added so far.

Data structures such as the Convex Hull Trick (CHT) and Li Chao Tree are well-known for performing “adding a line” and “querying the maximum (or minimum) value at a specific position \(x\)” efficiently.

In this problem, since the slope of the added lines \(B_j\) and the query coordinates \(B_i\) are not guaranteed to be monotonically increasing or decreasing, it is optimal to use a Li Chao Tree, which works with any order of insertions and queries.

---

Algorithm

Solution using Li Chao Tree

A Li Chao Tree is a data structure that allows us to find the maximum value for a query \(x\) in \(O(\log N)\) time by storing “the line that is most advantageous (achieves the maximum value) in that interval” in each node of a segment tree.

The specific steps are as follows:

1. Coordinate Compression: The values of \(x\) given as queries are only \(B_i\). We collect all \(B_i\) beforehand, sort them, remove duplicates, and register them as the coordinates (array \(X\)) corresponding to the leaves of the Li Chao Tree.
2. DP Transition: For each \(i = 0, 1, \ldots, N-1\) in this order, perform the following:
   • Query the Li Chao Tree to get the maximum value best_prev at \(x = B_i\).
   • Set \(DP[i] = A_i + \max(0, \text{best\_prev})\).
   • Add the line \(y = B_i \cdot x + DP[i]\) to the Li Chao Tree.
3. Updating the Answer: The maximum value of \(DP[i]\) over all \(i\) will be the maximum total score we want to find.

---

Complexity

• Time Complexity: \(O(N \log N)\)
  • Sorting for coordinate compression takes \(O(N \log N)\) time.
  • For each song \(i\), we query the Li Chao Tree and add a line to it, both in \(O(\log N)\) time. Repeating this \(N\) times yields an overall time complexity of \(O(N \log N)\), which easily runs within the time limit.
• Space Complexity: \(O(N)\)
  • The size of the coordinate-compressed array \(X\) and the Li Chao Tree (segment tree) is \(O(N)\).

---

Key Implementation Details

• Handling Initial Values: We set a very small value (-INF) to represent the initial state of the lines or the absence of a line. Since the score can be negative in this problem, we use a sufficiently small value (such as \(-3 \times 10^{18}\), which does not overflow within the 64-bit integer range) as INF.

• Processing the First Song: At the beginning of the loop (when \(i=0\)), no lines have been registered yet, so the query result from the Li Chao Tree will be -INF. Due to \(\max(0, \text{best\_prev})\), \(0\) is automatically chosen, and \(DP[0] = A_0\) is correctly computed.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 3e18;

struct Line {
    long long a, b;
    long long eval(long long x) const {
        if (b <= -INF) return -INF;
        return a * x + b;
    }
};

struct LiChaoTree {
    int n;
    vector<long long> X;
    vector<Line> tree;

    LiChaoTree(const vector<long long>& X_orig) {
        X = X_orig;
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
        n = 1;
        while (n < X.size()) n *= 2;
        while (X.size() < n) {
            X.push_back(X.back() + 1);
        }
        tree.assign(2 * n, {0, -INF});
    }

    void add_line(Line new_line) {
        add_line(1, 0, n - 1, new_line);
    }

    void add_line(int node, int l, int r, Line new_line) {
        int m = (l + r) / 2;
        bool left = new_line.eval(X[l]) > tree[node].eval(X[l]);
        bool mid = new_line.eval(X[m]) > tree[node].eval(X[m]);
        bool right = new_line.eval(X[r]) > tree[node].eval(X[r]);

        if (left && right) {
            tree[node] = new_line;
            return;
        }
        if (!left && !right) {
            return;
        }
        if (mid) {
            swap(tree[node], new_line);
        }
        if (left != mid) {
            add_line(2 * node, l, m, new_line);
        } else {
            add_line(2 * node + 1, m + 1, r, new_line);
        }
    }

    long long query(long long x) {
        int idx = lower_bound(X.begin(), X.end(), x) - X.begin();
        return query(1, 0, n - 1, idx);
    }

    long long query(int node, int l, int r, int idx) {
        long long res = tree[node].eval(X[idx]);
        if (l == r) return res;
        int m = (l + r) / 2;
        if (idx <= m) {
            res = max(res, query(2 * node, l, m, idx));
        } else {
            res = max(res, query(2 * node + 1, m + 1, r, idx));
        }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
    }

    LiChaoTree lct(B);

    long long ans = -INF;
    for (int i = 0; i < N; ++i) {
        long long best_prev = lct.query(B[i]);
        long long dp = A[i] + max(0LL, best_prev);
        ans = max(ans, dp);
        lct.add_line({B[i], dp});
    }

    cout << ans << "\n";

    return 0;
}

---

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