Summary

We consider a dynamic programming approach where the last song of the subsequence is fixed.
By treating \(B_j \times B_i\) in the transition formula as the value of a line, we can find the maximum value quickly using a Li Chao Tree.

Analysis

Let \(dp_i\) be the maximum score of a subsequence ending with song \(i\).

If we only choose song \(i\), the score is \(A_i\).

On the other hand, if we append song \(i\) after a subsequence ending with song \(j \ (j < i)\), the score becomes:

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

Therefore, the transition can be written as follows:

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

Here, \(0\) represents starting a new subsequence from song \(i\).

The final answer is:

\[ \max_i dp_i \]

---

A naive approach that checks all \(j < i\) for each \(i\) would take \(O(N^2)\) time.
Since \(N \leq 10^5\), this will not run within the time limit.

The key observation is that:

\[ dp_j + B_j \times B_i \]

in the transition can be viewed as the value of a line at \(x = B_i\).

For each song \(j\), let’s define the following line:

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

Then, we have:

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

In other words, for each \(i\), we need to efficiently find:

• The lines \(f_j\) formed by the previous songs \(j < i\)
• The maximum value among them at \(x = B_i\)

This can be achieved using a Li Chao Tree.

Algorithm

We process the songs from left to right in the following order:

1. Query the maximum value at \(x = B_i\) from the set of lines added so far.
2. Let this value be \(q\). We then set:

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

1. Record \(dp_i\) as a candidate for the answer.
2. To use song \(i\) for future transitions, add the line:

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

to the Li Chao Tree.

---

Specifically, this corresponds to the following in the code:

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

This represents:

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

Afterward,

add_line(b, dp)

adds the line:

\[ y = B_i x + dp_i \]

---

About Li Chao Tree

A Li Chao Tree is a data structure that can perform the following operations on a set of lines, both in about \(O(\log N)\) time:

• Add a line
• Find the maximum value at a given \(x\)

In this problem, the queried value \(x\) is always one of the \(B_i\).
Therefore, we collect all \(B_i\), sort them, and perform coordinate compression.

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

The Li Chao Tree only compares values on these xs coordinates.

Each line is managed in the form of:

\[ y = mx + c \]

For the lines added in this problem:

• Slope \(m = B_i\)
• Y-intercept \(c = dp_i\)

Complexity

Let \(M\) be the number of unique values of \(B_i\).
We have \(M \leq N\).

• Time Complexity: \(O(N \log M)\)
• Space Complexity: \(O(M)\)

Since \(M \leq N\), the overall complexity is:

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

Implementation Points

• Since \(dp_i\) can become large, you must use a sufficiently large integer type.

  • In Python, integers have arbitrary precision, so this is not an issue.

• If you call query when no lines have been added yet, it should return a very small value NEG.

  • In this case, q > 0 will be false, so the transition correctly defaults to starting a new subsequence with only song \(i\).

• Always add the line after calculating \(dp_i\) for the current song.

  • If you add it beforehand, the current song might be used as the previous song, which violates the condition \(j < i\).

• \(A_i\) and \(B_i\) can be negative.

  • Therefore, a simple greedy approach will not work.

  • It is crucial to formulate this as DP + Li Chao Tree, where “the best previous states are managed as lines”.

    Source Code

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()

---

This editorial was generated by gpt-5.5-high.