Boxing Club Scheduling – Median Revenue of Lewis’s Optimal Schemes

Lewis runs a boxing club with four members: Lewis, Valtteri, Max, and Checo. In each of n matches he organizes, he must choose two fighters from these four, but with the following restrictions:

• If the match is between Lewis and Valtteri, it brings in a_i revenue.
• If the match is between Valtteri and one of the stars (Max or Checo), it earns b_i revenue.
• If the match is between the two stars (Max and Checo), it earns c_i revenue.

It is guaranteed that for every match i, \[ 1 \le a_{i} < b_{i} < c_{i} \le 10^9. \]

Moreover, Lewis refuses to pit himself against any star – whenever a star appears the opponent will be Valtteri. In other words, the only valid match‐ups are:

• Option 1: Lewis vs Valtteri (earning a_i).
• Option 2: Valtteri vs a star (earning b_i).
• Option 3: Max vs Checo (earning c_i).

However, booking stars is subject to scheduling constraints. For each star the following must hold: if we denote the first match in which, say, Max appears by \(p_m\) and his last match by \(q_m\) (and similarly Checo by \(p_c\) and \(q_c\)), then \[ q_m - p_m + 1 \le t_m \quad\text{and}\quad q_c - p_c + 1 \le t_c. \] That is, each star’s span (from first to last appearance) cannot exceed a given limit.

The twist is in the definition of Lewis’s optimal scheme: consider a scheme as an array of 2n numbers (each adjacent pair representing a match). A scheme is called optimal if no single change in any one position (that is, changing one fighter in one match – while keeping the overall scheme valid) can produce a strictly higher total revenue.

Note that although a scheme fulfilling this local optimality condition may not be globally revenue‐maximizing and there may be several optimal schemes, Lewis will choose one of them uniformly at random. Your task is to compute the median ticket revenue over all possible Lewis’s optimal schemes (if there is only one scheme then its revenue is the median). Output the answer rounded to one decimal place.

Additional details:

1. There will be exactly n matches, with \(1 \le n \le 2\times10^5\).
2. For the i-th match, the revenue values \(a_i, b_i, c_i\) are given (with \(a_i < b_i < c_i\)).
3. The scheduling limits for the stars are given as t_m and t_c.

---

Observations and a key idea:

A careful analysis shows that since \(a_i < b_i < c_i\), a match assigned Option 1 (Lewis vs Valtteri) is always improvable – one can change it to Option 2 (giving a revenue increase of \(b_i - a_i\)) while meeting the scheduling constraint (a star appearing only once yields a span of 1 which is valid). Hence, in any optimal scheme, every match must be booked either as Option 2 or Option 3. Furthermore, note that if an Option 2 match is isolated (i.e. not contiguous to any other match in which both stars appear), upgrading it to Option 3 will be valid (its resulting star span will be 1 and thus within limits). This forces the following structure for a locally optimal scheme:

Define \(X = \min(t_m, t_c)\). Then there are two cases:

• Case 1: If \(n \le X\) then assigning Option 3 to every match is valid. The total revenue is \(\sum_{i=1}^n c_i\).
• Case 2: If \(n > X\) then the only ways to prevent an Option 2 match from being upgradable is to have a contiguous block of Option 3 matches of length exactly \(X\) at one end of the schedule. There turn out to be exactly two optimal schemes:
  1. Option 3 for matches 1 to \(X\) and Option 2 for matches \(X+1\) to \(n\);
  2. Option 2 for matches 1 to \(n-X\) and Option 3 for matches \(n-X+1\) to \(n\).
  Their total revenues are: \[ R_1 = \left(\sum_{i=1}^{X} c_i\right) + \left(\sum_{i=X+1}^{n} b_i\right), \quad R_2 = \left(\sum_{i=1}^{n-X} b_i\right) + \left(\sum_{i=n-X+1}^{n} c_i\right). \] The median revenue is the average \(\frac{R_1+R_2}{2}\) (if both values are equal then that value is the median).

Your task is to compute the median revenue (rounded to one decimal) among the set of Lewis’s optimal schemes that might be chosen.

inputFormat

The first line contains three integers n, t_m and t_c (\(1 \le n \le 2\times10^5\), \(1 \le t_m, t_c \le n\)).

Then follow n lines. The i-th of these lines contains three integers a_i, b_i and c_i (\(1 \le a_i < b_i < c_i \le 10^9\)).

outputFormat

Output a single number – the median revenue among all of Lewis’s optimal schemes, rounded to one decimal place.

sample

1 1 1
1 2 3

3.0