Overview

This is a problem of maximizing profit when accepting some events such that they don’t overlap. Through formula transformation, we reduce it to “interval scheduling with weights on each event (weighted interval selection)” and solve it with DP.

Analysis

1) Rephrasing the profit formula as “maximizing the score of accepted events”

The profit is $\(|S|\times B - \sum_{i\notin S} C_i\)\( Here, \)\sum_{i\notin S} Ci\( is the total sum of all \)C\( minus the sum of \)C$ for accepted events, so: [ |S|B - \left(\sum{i=1}^N Ci - \sum{i\in S} Ci\right) = -\sum{i=1}^N Ci + \sum{i\in S}(B + C_i) ]

In other words: - \(-\sum C_i\) is constant regardless of the selection - What we need to maximize is \(\sum_{i\in S}(B+C_i)\)

Therefore, by treating “selecting event \(i\) gives weight \(W_i=B+C_i\)”, we just need to solve maximizing the total weight of a set of non-overlapping intervals.

2) Why a naive solution doesn’t work

Exhaustive search while checking overlaps would require \(2^N\) cases, which is infeasible.
Also, even with DP, the state tends to explode if we track “which event was selected last.” However, for interval problems, by sorting by end time, we can use binary search to find “the last compatible event before the current one,” allowing a 1-dimensional DP.

3) Handling half-open intervals

Since intervals are \([L_i, R_i)\), intervals that touch at endpoints (\(R_j = L_i\)) do not overlap.
Therefore, the compatibility condition is: $\(R_j \le L_i\)$ We handle this with binary search.

Algorithm

1. Compute the total sum of \(C\) for all events: \(\text{sumC}=\sum C_i\).
2. Represent each event as a tuple \((R, L, W)\) where:
   • End time \(R\)
   • Start time \(L\)
   • Weight \(W = B + C\)

Sort these in ascending order of \(R\). 3. Define the DP: - \(dp[i]\) = “maximum total weight obtainable when considering the first \(i\) events (1..i) after sorting” 4. Transition: - Don’t select the \(i\)-th event (index \(i-1\) in the array): \(dp[i-1]\) - Select it: optimal value up to the last compatible event \(dp[p] + W\)

Here, \(p\) is “the number of events whose end time is \(\le L\)”, so for the end time array ends: $\(p = \text{bisect\_right}(ends, L)\)\( (all events up to position \)p-1$ satisfying ends[p-1] <= L are compatible).

Therefore: [ dp[i] = \max(dp[i-1],\ dp[p] + W) ] 5. The final answer, converted back to the original profit, is: [ \text{ans} = -\text{sumC} + dp[N] ]

Complexity

• Time complexity: \(O(N\log N)\) (sorting \(O(N\log N)\) + binary search \(O(\log N)\) per DP transition, \(N\) times)
• Space complexity: \(O(N)\) (event array, ends, dp, etc.)

Implementation Notes

• Since the overlap check uses half-open intervals \([L,R)\), the compatibility condition is \(R \le L\). Using bisect_right(ends, L) for the binary search is appropriate.

• The DP array is initialized with dp[0]=0, and dp[i] represents “considering the first i events,” so we can directly reference dp[p].

• The answer can be negative, so simply output -sumC + dp[N] as is.

  Source Code

import sys
import bisect

def main():
    input = sys.stdin.buffer.readline
    N, B = map(int, input().split())
    events = []
    sumC = 0
    for _ in range(N):
        L, R, C = map(int, input().split())
        sumC += C
        events.append((R, L, B + C))

    events.sort()  # sort by end time R

    ends = [0] * N
    Ls = [0] * N
    Ws = [0] * N
    for i, (R, L, W) in enumerate(events):
        ends[i] = R
        Ls[i] = L
        Ws[i] = W

    dp = [0] * (N + 1)
    for i in range(1, N + 1):
        L = Ls[i - 1]
        W = Ws[i - 1]
        p = bisect.bisect_right(ends, L)  # number of intervals with end <= L
        cand = dp[p] + W
        dp[i] = dp[i - 1] if dp[i - 1] >= cand else cand

    ans = -sumC + dp[N]
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.