P8209 [THUPC 2022 Preliminary] Schedule Planning

Lewis loves boxing, so he founded a boxing club and hoped to raise money for his training by selling tickets for exhibition matches. Unfortunately, Lewis is not very popular, so the club has only two members—Lewis and his close friend Valtteri. The audience soon got tired of seeing only the two of them every night, tickets stopped selling, and the club was on the verge of bankruptcy. When things get tough, you look for changes, so Lewis decided to try to save his club by inviting guest fighters. With enough money, Lewis quickly invited two boxing stars—Max and Checo—as special guests to join the club. In the next season, Lewis will arrange a total of $n$ $(1 \le n \le 2*10^5)$ matches. Each match selects 2 out of the 4 current members to fight. For the $i$-th $(1 \le i \le n)$ match: - If it is a match between Lewis and Valtteri, it can sell tickets worth $a_i$ yuan. - If it is a match between one of them and a star, it can sell tickets worth $b_i$ yuan. - If it is a match between the two stars Max and Checo, it can sell tickets worth $c_i$ yuan. The audience likes high-level matches between stars, not the weak fights between Lewis and Valtteri, so $1 \le a_i < b_i < c_i \le 10^9$. In addition, the following requirements must be satisfied when scheduling the matches: 1. Since the stars are very busy, they only agree to stay in Lewis’s club for at most $t_m, t_c$ matches, respectively. Let Max’s first attended match be match $p_m$ and his last be match $q_m$, and Checo’s first attended match be match $p_c$ and his last be match $q_c$. Then we must have $q_m - p_m + 1 \le t_m$ and $q_c - p_c + 1 \le t_c$. 2. Lewis knows he is no match for the two stars, and he does not want to be beaten up and knocked out, so he will not schedule any match between himself and either star. (In other words, the job of getting beaten is secretly assigned by Lewis to his close friend Valtteri. Let us mourn for the poor “tool person” Valtteri.) 3. Lewis wants to maximize his total income, but he is not very smart. So, if a plan satisfies the following condition, he believes it achieves “maximum income”. Definition (“Lewis’s optimal plan”): A plan can be viewed as a sequence of length $2n$, where the $(2i-1)$-th and $2i$-th elements are the two fighters in match $i$. If, by changing any one position of the sequence, it is impossible to obtain a legal plan whose income is strictly greater than the current income, then this plan is called “Lewis’s optimal plan”. You quickly notice that “Lewis’s optimal plan” does not necessarily maximize the total income and may not be unique. It is known that Lewis will choose uniformly at random from all “Lewis’s optimal plans”. (Two plans are the same if and only if the matchups on every day are the same. Note that Max vs Valtteri and Checo vs Valtteri sell the same tickets, but they are considered two different plans.) Then, among all plans that Lewis may finally choose, what is the median of the ticket income? (Output the answer rounded to one decimal place.)

Line $1$: Three positive integers $n, t_m, t_c$, as defined in the statement. Next $n$ lines: Each line contains three positive integers $a_i, b_i, c_i$, representing the ticket price in the three cases.

Output one number in one line, representing the median of the ticket income among all plans that Lewis may finally choose.

[Sample Explanation] Lewis’s “maximum income plan” has the following $4$ possibilities: - Max vs Checo, Lewis vs Valtteri, ticket income is $100+1=101$. - Valtteri vs Max, Valtteri vs Checo, ticket income is $10+2=12$. - Valtteri vs Checo, Valtteri vs Max, ticket income is $10+2=12$. - Lewis vs Valterri, Max vs Checo, ticket income is $1+3=4$. The median is $\frac{12+12}{2} = 12$. [Constraints] For $100\%$ of the testdata, $1 \le n, t_m, t_c \le 2*10^5$, and $1 \le a_i < b_i < c_i \le 10^9$. Translated by ChatGPT 5