Official Editorial

Explanation

Binary search on the answer for the minimum number of tickets, $t$, to sell to make the total ecological contribution to at least $k$.

Let's try to determine the maximum contribution attainable with $t$ tickets.

The problem indicates that only $x\%$ of the $a$-th ticket and $y\%$ of the $b$-th ticket could contribute to the total ecological contribution. We can precompute these multipliers $pct$ (either $0$, $x$, $y$, or $x+y$ depending on the ticket) over $t$ tickets, then greedily match the largest multiplier with the highest value ticket. This can be done by sorting the multipliers $pct$ and tickets $p$ in decreasing order; then the maximum total ecological contribution would be $\sum\limits_{i=1}^{t} p_i \cdot pct_i$.

Implementation

Time Complexity: $\mathcal{O}(N\log^2 N)$

Copy
from math import gcd

for _ in range(int(input())):
	ticket_num = int(input())
	tickets = sorted([int(i) for i in input().split()], reverse=True)
	prog1 = [int(i) for i in input().split()]
	prog2 = [int(i) for i in input().split()]
	min_revenue = int(input())
	# the frequency of both programs including a single ticket
	combo_freq = prog1[1] * prog2[1] // gcd(prog1[1], prog2[1])