Overview

This problem asks us to choose a subsequence from \(N\) songs while preserving their order, to maximize the total score. The total score is the sum of the individual scores of the selected songs plus the sum of the products of the compatibility values of consecutive songs. This can be solved using Dynamic Programming (DP) and a data structure to quickly find the maximum value of lines (Li Chao Tree).

Observation

First, let us formulate the total score when the selected subsequence is \(c_1, c_2, \ldots, c_k\). According to the problem statement, the score is defined as \(A_{c_1} + \sum_{j=2}^{k} (A_{c_j} + B_{c_{j-1}} B_{c_j})\). Expanding this expression, we can rewrite it as follows:

\[ \sum_{j=1}^{k} A_{c_j} + \sum_{j=1}^{k-1} B_{c_j} B_{c_{j+1}} \]

From this formula, we can see that when we append a new song \(i\) to the end of the subsequence, if the immediately preceding song is \(j\), the score increment is \(A_i + B_j B_i\).

Here, let us consider DP. We define dp[i] as “the maximum score of a subsequence where the last selected song is \(i\)”. The transition formula is as follows:

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

The reason \(0\) is included in the \(\max\) is that if \(i\) is the first song of the subsequence (the 1st song), the increment is only \(A_i\).

If we calculate this transition formula as is, it takes \(O(N^2)\) time because we search all past \(j\) for each \(i\). Under the constraint \(N \le 10^5\), this will result in TLE (Time Limit Exceeded).

Therefore, we focus on the inner part \(\max_{j < i} (dp[j] + B_j \cdot B_i)\). If we consider \(B_i\) as a variable \(x\), this expression reduces to the problem of “finding the maximum value at \(x = B_i\) among a set of lines with slope \(B_j\) and y-intercept \(dp[j]\)”. Such queries can be processed efficiently in \(O(\log V)\) time (where \(V\) is the range of \(x\)-coordinates) using a data structure called the Li Chao Tree.

Algorithm

We speed up the DP transitions using the Li Chao Tree.

The Li Chao Tree is a data structure that can insert lines and query the maximum (or minimum) value at a specific \(x\)-coordinate, each in \(O(\log V)\) time.

1. For song \(i\), query the Li Chao Tree at \(x = B_i\) to obtain the maximum value of the past lines \(\max_{j < i} (dp[j] + B_j \cdot B_i)\).
2. Compare the obtained value with \(0\), take the larger one, and add \(A_i\) to find \(dp[i]\).
3. Update the maximum value of \(dp[i]\) as a candidate for the answer.
4. For future transitions, insert a new line with slope \(B_i\) and y-intercept \(dp[i]\) into the Li Chao Tree.

As an initial state, we insert a line that always returns \(0\) regardless of \(x\) (\(y = 0\)). This simplifies the process when choosing the first song.

Complexity

• Time Complexity: \(O(N \log V)\)
  • \(V\) is the width of the range of possible values for \(B_i\) (\(2 \times 10^6\)). Since we perform one line insertion and one maximum value query at each step, the overall time complexity is \(O(N \log V)\).
• Space Complexity: \(O(V)\)
  • Since the Li Chao Tree has segment tree nodes based on the range of \(x\)-coordinates, it requires \(O(V)\) memory.

Implementation Details

• Adding the Initial Line: We add a line with slope \(0\) and y-intercept \(0\) using lct.add(0, 0). This allows us to treat the score increment as \(0\) when we do not choose any past song (i.e., making the current song the first song).

• Handling Negative Scores: The song score \(A_i\) and compatibility value \(B_i\) can be negative. If max_val becomes negative, it is replaced with \(0\) by max(0LL, max_val), which prevents forcibly connecting to past songs when the compatibility bonus is negative.

• Overflow Prevention: Since \(A_i, B_i\) can be up to \(10^6\) and \(N \le 10^5\), the score can grow up to around \(10^{17}\). We must use long long types and set the initial minimum value (-INF) to a sufficiently small value (e.g., \(-10^{18}\)).

  Source Code

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

using namespace std;

const long long MIN_X = -1000000;
const long long MAX_X = 1000000;
const long long INF = 1e18;

struct LiChaoTree {
    struct Line {
        long long a, b;
    };
    vector<Line> data;
    
    LiChaoTree() {
        data.assign(4 * (MAX_X - MIN_X + 1), {0, -INF});
    }
    
    long long eval(const Line& l, long long x) const {
        return l.a * x + l.b;
    }
    
    void add_line(Line new_line, int node, long long L, long long R) {
        Line current = data[node];
        long long mid = L + (R - L) / 2;
        
        bool left = eval(new_line, L) > eval(current, L);
        bool m = eval(new_line, mid) > eval(current, mid);
        
        if (m) {
            swap(data[node], new_line);
        }
        if (R - L == 1) return;
        
        if (left != m) {
            add_line(new_line, 2 * node, L, mid);
        } else {
            add_line(new_line, 2 * node + 1, mid, R);
        }
    }
    
    void add(long long a, long long b) {
        add_line({a, b}, 1, MIN_X, MAX_X + 1);
    }
    
    long long query(long long x, int node, long long L, long long R) const {
        long long val = eval(data[node], x);
        if (R - L == 1) return val;
        long long mid = L + (R - L) / 2;
        if (x < mid) {
            return max(val, query(x, 2 * node, L, mid));
        } else {
            return max(val, query(x, 2 * node + 1, mid, R));
        }
    }
    
    long long query(long long x) const {
        return query(x, 1, MIN_X, MAX_X + 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    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;
    lct.add(0, 0); // クエリ結果が負の場合に0を選択するためのベースライン
    
    long long ans = -INF;
    for (int i = 0; i < n; ++i) {
        long long max_val = lct.query(B[i]);
        long long dp_i = A[i] + max(0LL, max_val);
        ans = max(ans, dp_i);
        lct.add(B[i], dp_i);
    }
    
    cout << ans << "\n";
    return 0;
}

This editorial was generated by or-glm5.2-high.