Overview

This problem asks us to find the maximum score of a playlist ending with each song using dynamic programming. Focusing on the fact that the compatibility product of adjacent songs \(B_{c_{j-1}} \times B_{c_j}\) can be viewed as a “linear evaluation”, we speed up the calculation using a Li Chao Tree (maximum query on a set of lines).

Analysis

DP Formulation

We define \(\mathrm{dp}[i]\) as “the maximum total score of a playlist ending with song \(i\)”.

When song \(i\) is the last song, the state immediately preceding it can be one of the following two cases:

• Song \(i\) alone (\(k=1\)): The score is \(A_i\).
• Placing song \(i\) after some song \(j\) (\(j<i\)): The score \(A_i\) of the new song and the bonus \(B_j \times B_i\) are added to the score of the previous playlist \(\mathrm{dp}[j]\), resulting in \(\mathrm{dp}[j] + A_i + B_j \times B_i\).

Therefore,

\[ \mathrm{dp}[i] = A_i + \max\Bigl(0,\ \max_{j<i}\bigl(\mathrm{dp}[j] + B_j \times B_i\bigr)\Bigr) \]

(where the \(0\) inside the \(\max\) corresponds to the case of “starting a new playlist with song \(i\)”). The answer is the maximum value of \(\mathrm{dp}[i]\) over all \(i\).

Issue with the Naive Approach

Computing the above formula naively takes \(O(N^2)\) because we check all \(j < i\) for each \(i\), which will result in TLE (Time Limit Exceeded) for \(N \le 10^5\).

How to Speed It Up

Here is the key observation. If we treat the expression inside the \(\max\):

\[ \mathrm{dp}[j] + B_j \times B_i \]

as a linear function of the variable \(x = B_i\), we get:

\[ f_j(x) = B_j \cdot x + \mathrm{dp}[j] \]

which is a line with slope \(B_j\) and y-intercept \(\mathrm{dp}[j]\). Then, \(\max_{j<i}(\cdots)\) is exactly the operation to find:

the maximum value when evaluating the set of lines added so far at the point \(x = B_i\).

This is exactly the type of operation that Convex Hull Trick or Li Chao Tree excels at.

In this problem, \(B_i\) is not necessarily monotonic, and the slopes of the added lines are not in any specific order. Therefore, we use a Li Chao Tree, which can handle queries at arbitrary points and insertions of lines with arbitrary slopes.

Algorithm

We process the songs in order \(i=1,2,\dots,N\) and perform the following:

1. Query: Evaluate the current set of lines at point \(x = B_i\) to get the maximum value best.
2. DP Update: Calculate \(\mathrm{dp}[i] = A_i + \max(0, \text{best})\) and update the overall answer.
3. Line Addition: Add the line with slope \(B_i\) and y-intercept \(\mathrm{dp}[i]\) to the Li Chao Tree.

This ensures that we only query against the lines from \(j < i\), maintaining the correctness of the DP dependencies.

Key Points of Li Chao Tree

A Li Chao Tree is a data structure that manages “the maximum line at the representative point of an interval” on a segment tree whose leaves correspond to the candidate \(x\)-coordinates. In this problem, the values that appear as evaluation points \(x\) are always some \(B_i\), so we coordinate-compress \(B_i\) and assign them to the leaves.

• addLine: Keeps the line that is larger at the midpoint of the interval in the current node, and recursively pushes the losing line down to one of the children.
• query: Traverses down from the root to the target leaf, evaluating the line at each visited node to find the maximum value.

Complexity

• Time Complexity: \(O(N \log N)\)
  (Sorting for coordinate compression takes \(O(N \log N)\), and addition/query for each song on the Li Chao Tree takes \(O(\log N)\).)
• Space Complexity: \(O(N)\)
  (The number of segment tree nodes is proportional to the number of unique coordinates.)

Key Implementation Points

• Handling the “start alone” case: Do not forget the \(\max(0, \cdot)\) in \(\mathrm{dp}[i] = A_i + \max(0, \text{best})\). If all \(\mathrm{dp}[j] + B_j B_i\) are negative, it is better to start a new playlist with song \(i\).

• Initial values and overflow prevention: To represent the absence of a line, we use a sufficiently small constant NEG = LLONG_MIN/4 as the y-intercept. Since the value can grow large with m*x, using LLONG_MIN directly risks overflow/underflow, so we leave some margin.

• Using 64-bit integers: Since \(A_i\) and \(B_i\) can be up to \(10^6\) and we compute products and sums, we use long long (64-bit) for calculations. The problem statement also guarantees that the answer fits within a 64-bit integer.

• Coordinate Compression: Since the evaluation points \(x\) are always one of the \(B_i\) from the input, we sort and remove duplicates from \(B_i\) to map them to leaf indices.

  Source Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NEG = LLONG_MIN/4;

int sz;
vector<ll> xs;
vector<ll> segm, segb; // line: m*x+b ; empty if b==NEG

inline ll evalLine(int node, ll x){
    if(segb[node]==NEG) return NEG;
    return segm[node]*x + segb[node];
}

void addLine(int node,int l,int r, ll m, ll b){
    while(true){
        int mid=(l+r)/2;
        ll cl = (segb[node]==NEG)?NEG:(segm[node]*xs[l]+segb[node]);
        ll cm = (segb[node]==NEG)?NEG:(segm[node]*xs[mid]+segb[node]);
        ll nl = m*xs[l]+b;
        ll nm = m*xs[mid]+b;
        bool left = nl > cl;
        bool midb = nm > cm;
        if(midb){
            swap(segm[node], m);
            swap(segb[node], b);
        }
        if(l==r) return;
        if(left != midb){
            node=2*node; r=mid;
        } else {
            node=2*node+1; l=mid+1;
        }
    }
}

ll query(int node,int l,int r,int pos){
    ll res = evalLine(node, xs[pos]);
    while(l!=r){
        int mid=(l+r)/2;
        if(pos<=mid){ node=2*node; r=mid; }
        else { node=2*node+1; l=mid+1; }
        res = max(res, evalLine(node, xs[pos]));
    }
    return res;
}

int main(){
    int N;
    scanf("%d",&N);
    vector<ll> A(N), B(N);
    for(int i=0;i<N;i++){
        scanf("%lld %lld",&A[i],&B[i]);
        xs.push_back(B[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    sz = xs.size();
    segm.assign(4*sz, 0);
    segb.assign(4*sz, NEG);
    
    ll ans = NEG;
    for(int i=0;i<N;i++){
        int pos = lower_bound(xs.begin(), xs.end(), B[i]) - xs.begin();
        ll best = query(1,0,sz-1,pos);
        ll cur = A[i] + max(0LL, best);
        ans = max(ans, cur);
        addLine(1,0,sz-1, B[i], cur);
    }
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.