Overview

This is a problem where you select some events from multiple options such that their times do not overlap, maximizing the “profit” obtained. By rearranging the formulas, this problem can be reduced to the classic dynamic programming (DP) form known as the “weighted interval scheduling problem.”

Analysis

1. Simplifying the Objective Function

First, let’s simplify the expression for the “profit” we want to maximize. Let \(S\) be the set of accepted events and \(T\) be the set of all events. The profit is expressed as: $\(\text{Profit} = |S| \times B - \sum_{i \in T \setminus S} C_i\)$

Here, \(\sum_{i \in T \setminus S} C_i\) (the total compensation cost of rejected events) can be rewritten as: $\(\sum_{i \in T \setminus S} C_i = \left( \sum_{i \in T} C_i \right) - \left( \sum_{i \in S} C_i \right)\)$

Substituting this into the profit expression: $\(\begin{aligned} \text{Profit} &= |S| \times B - \left( \sum_{i \in T} C_i - \sum_{i \in S} C_i \right) \\ &= \sum_{i \in S} B + \sum_{i \in S} C_i - \sum_{i \in T} C_i \\ &= \sum_{i \in S} (B + C_i) - \sum_{i \in T} C_i \end{aligned}\)$

\(\sum_{i \in T} C_i\) is a constant value regardless of which events are chosen. Therefore, solving this problem is equivalent to solving: “Given that each event \(i\) has weight \(W_i = B + C_i\), select non-overlapping events to maximize the total weight \(\sum_{i \in S} W_i\).”

2. Coordinate Compression

Since the start times \(L_i\) and end times \(R_i\) of events can be as large as \(10^9\), they cannot be directly used as array indices. However, the only meaningful time points are the at most \(2N\) values that appear as endpoints (\(L_i\) and \(R_i\)) of each event. Therefore, by performing coordinate compression — sorting all appearing time points in ascending order and renumbering them as \(0, 1, 2, \dots\) — we can bring them into a computable range.

3. Dynamic Programming (DP)

Let the compressed time points be \(t_0, t_1, \dots, t_{M-1}\). We define the following DP: - \(dp[i] = \) the maximum total weight when selecting non-overlapping events among those that end by time \(t_i\)

The transitions are as follows: 1. Not selecting any event: \(dp[i] = dp[i-1]\) 2. Selecting event \(j\) that ends at time \(t_i\): \(dp[i] = \max(dp[i], dp[\text{index of event } j\text{'s start time}] + W_j)\)

By computing this in order, the final answer is \(dp[M-1] - \sum C_i\).

Algorithm

1. For each event \(i\), compute the weight \(W_i = B + C_i\).
2. Collect all \(L_i, R_i\), remove duplicates, sort them, and create a mapping for coordinate compression.
3. For each compressed end time \(R_i\), maintain a list of events that end at that time.
4. Initialize the DP table and compute transitions sequentially from time \(0\).
5. Subtract the precomputed sum of \(C_i\) over all events from the obtained maximum value.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting the time points (coordinate compression) takes \(O(N \log N)\).
  • The DP transitions check each event once, taking \(O(N)\).
• Space complexity: \(O(N)\)
  • The coordinate compression map, DP table, and event lists use \(O(N)\) memory.

Implementation Notes

• Handling half-open intervals: As stated in the problem, intervals are \([L_i, R_i)\), so even if an end time \(R_i\) coincides with another event’s start time \(L_j\), they are not considered overlapping. In the DP transition, using dp[l_idx] + w correctly inherits the result of another event that ends exactly at time \(L_i\), so this is handled correctly.

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # Fast I/O: read all input at once and use an iterator for memory and time efficiency
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # Use an iterator to process data efficiently
    data_iter = iter(map(int, input_data))
    
    try:
        N = next(data_iter)
        B = next(data_iter)
    except StopIteration:
        return
    
    events = []
    coords_set = set()
    total_c = 0
    
    # Parse events and collect unique coordinates for compression
    for _ in range(N):
        try:
            l = next(data_iter)
            r = next(data_iter)
            c = next(data_iter)
            # The weight of an event is the profit B plus the avoided cancellation cost C_i
            w = B + c
            events.append((l, r, w))
            coords_set.add(l)
            coords_set.add(r)
            total_c += c
        except StopIteration:
            break
        
    # Coordinate compression: Map large time values to a range [0, M-1]
    # sorted_coords: all unique L_i and R_i in ascending order
    sorted_coords = sorted(coords_set)
    # coord_map: mapping from time to its index in sorted_coords
    coord_map = {val: i for i, val in enumerate(sorted_coords)}
    M = len(sorted_coords)
    
    # Group intervals by their compressed end time index
    adj = [[] for _ in range(M)]
    for l, r, w in events:
        adj[coord_map[r]].append((coord_map[l], w))
        
    # dp[i]: max weight of non-overlapping intervals ending at or before sorted_coords[i]
    dp = [0] * M
    for i in range(M):
        # The current max weight is at least the max weight from the previous coordinate
        if i > 0:
            dp[i] = dp[i-1]
        
        # Check all events ending exactly at the current coordinate sorted_coords[i]
        # Each event can be combined with the best set of events ending at or before its start time.
        # Problem states that if one ends at t and another starts at t, they do not overlap.
        # This is handled because dp[l_idx] represents the max weight of intervals ending at or before sorted_coords[l_idx].
        for l_idx, w in adj[i]:
            new_w = dp[l_idx] + w
            if new_w > dp[i]:
                dp[i] = new_w
                
    # Final maximum profit calculation
    # The objective is to maximize: |S| * B - Sum_{i not in S} C_i
    # This is equivalent to maximizing: Sum_{i in S} (B + C_i) - Sum_{all i} C_i
    # dp[M-1] gives the maximum Sum_{i in S} (B + C_i) for non-overlapping intervals.
    if M > 0:
        print(dp[M-1] - total_c)
    else:
        # If N=0 (though N >= 1 by constraints), profit is 0
        print(0)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.