Overview

“Minimizing the cost of removal” can be rephrased as “maximizing the ‘cost saved by not removing’ corresponding to the books we keep (a strictly increasing subsequence).” We efficiently compute the weighted longest increasing subsequence (maximum weight increasing subsequence).

Analysis

Since the remaining books cannot be rearranged, the set of books we keep must form a subsequence that preserves the original order. The condition requires that the page counts are strictly monotonically increasing, i.e., \(A_{i_1} < A_{i_2} < \cdots\) must hold.

Here, the objective is to “minimize the total fees for removed books,” but if we let the total sum of all fees be \(S=\sum C_i\), then:

• Fees paid for removed books \(= S - (\text{fees saved by not removing})\)
• Fees saved by not removing \(=\) “sum of \(C\) for the books we keep”

Therefore, the problem can be rephrased as follows:

When keeping books such that page counts are strictly increasing, maximize the total \(C\) of the kept books.
The answer is \(S - (\text{maximum value})\).

A naive approach defines \(dp[i] =\) maximum total when book \(i\) is the last one kept, computing
\(dp[i] = C_i + \max\{dp[j] \mid j<i, A_j < A_i\}\)
which is \(O(N^2)\). For \(N=5000\), this is borderline and can be heavy depending on the implementation (we’d prefer to improve it for more breathing room).
We accelerate this by using a data structure that can quickly retrieve “the maximum value over the range satisfying \(A_j < A_i\).”

Algorithm

1. Coordinate Compression

Since \(A_i\) can be up to \(10^9\), it is impractical to use it directly as an array index.
We sort the unique values of \(A\), and convert each \(A_i\) to a rank \(r_i\) in the range \(1..M\) (coordinate compression).

2. Managing “Prefix Maximum” with a BIT (Fenwick Tree)

A BIT normally handles prefix sums, but by replacing the operation with “maximum,” we can perform:

• query(x): maximum \(dp\) value over the range where the compressed value is \(\le x\)
• update(x, v): update position \(x\) with \(\max(\text{current}, v)\)

in \(O(\log M)\) time.

3. DP Transition

When “keeping” book \(i\), the previously kept book must have a smaller \(A\) value, so using the compressed rank \(r\):

• \(\text{bestPrev} = \max\{dp \mid \text{rank} \le r-1\} = \text{query}(r-1)\)
• \(dp = \text{bestPrev} + C_i\)

We then call update(r, dp). The overall maximum best is the “maximum total of fees that can be saved.”

Finally, the answer is \(\sum C_i - best\).

Complexity

• Time complexity: \(O(N \log N)\) (sorting for coordinate compression \(O(N\log N)\) + BIT operations for each element \(O(\log N)\))
• Space complexity: \(O(N)\) (compressed array and BIT)

Implementation Notes

• Since we require strictly increasing, the transition must use query(r-1) (books with the same page count cannot be chained).

• The BIT must be implemented to hold “maximum” instead of “sum” (bit[i] = max(bit[i], v)).

• \(C_i\) and the total can be as large as \(10^9 \times 5000\), so depending on the language, 64-bit integers may be required (Python has no issue).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    A = data[1:1+n]
    C = data[1+n:1+2*n]

    xs = sorted(set(A))
    m = len(xs)
    rank = {v: i+1 for i, v in enumerate(xs)}  # 1-indexed

    bit = [0] * (m + 2)

    def update(i, v):
        while i <= m:
            if v > bit[i]:
                bit[i] = v
            i += i & -i

    def query(i):
        res = 0
        while i > 0:
            if bit[i] > res:
                res = bit[i]
            i -= i & -i
        return res

    total = sum(C)
    best = 0
    for a, c in zip(A, C):
        r = rank[a]
        dp = query(r - 1) + c
        update(r, dp)
        if dp > best:
            best = dp

    print(total - best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.