907. The Strongest Team You Can Field
Each of n players has a SPEED and an EFFICIENCY. A team of at most k
players is rated
(total speed of the team) x (smallest efficiency in the team)
Print the best rating any team of one to k players can reach.
``` speeds 2 10 3 1 5 8, efficiencies 5 4 3 9 7 2, k = 2 -> 60 players 2 and 5: speeds 10 + 5 = 15, efficiencies min(4, 7) = 4
speeds 2 10 3 1 5 8, efficiencies 5 4 3 9 7 2, k = 3 -> 68 players 1, 2 and 5: speeds 2 + 10 + 5 = 17, min efficiency 4
one player, speed 7, efficiency 3 -> 21 ```
## What most people try first
The two factors pull against each other: adding a player always raises the
total speed and can only lower the minimum efficiency. So neither "take the k
fastest" nor "take the k most efficient" is right, and the first example
shows it, since the fastest two are speeds 10 and 8 with efficiencies 4 and 2,
giving 18 * 2 = 36, well under 60.
Enumerating teams is C(n, 1) + ... + C(n, k). At n = 20 and k = 10 that is
already 616665, and n reaches 10^5.
## The method: fix the weakest member
There are only n possible values for the minimum efficiency, one per player.
Fix a player j and ask for the best team whose minimum efficiency is exactly
e[j]. Every other member must have efficiency at least e[j], and subject to
that the only thing to do is make the total speed as large as possible.
Sort the players by efficiency DESCENDING and sweep. When the sweep reaches
j, the players already seen are exactly those with efficiency at least e[j].
Keep the k largest speeds among them in a MIN-heap, so the slowest member of
the current team sits at the top and is the one evicted.
sort players by efficiency descending
h = empty min-heap of speeds, s = 0, best = 0
for each player (speed, eff) in that order:
push speed onto h; s = s + speed
if size(h) > k: s = s - pop the smallest speed from h
best = max(best, s * eff)
print best
## Why it is correct
The candidate examined at step j is a legal team: every member was seen at or
before j, so every member has efficiency at least e[j], so the team's actual
minimum efficiency is at least e[j] and its true rating is at least
s * e[j]. No candidate therefore overstates the answer.
And the optimum is reached. Take an optimal team and let j be its member with
the smallest efficiency. At step j the sweep holds the k largest speeds
among all players with efficiency at least e[j], which is a superset of the
optimal team's members, so the heap's total speed is at least the optimal
team's total speed. Multiplying by the same e[j] gives a value at least the
optimum. Combined with the previous paragraph, the maximum over all steps is
exactly the answer.
Note that the team of fewer than k players is never a special case: the heap
simply has not filled yet, and best is updated on every step.
## The boundary that breaks a careless implementation
The heap must be a MIN-heap of speeds even though the answer is a maximum. The instinct to reach for a max-heap is strong and gives the wrong eviction: you want to throw away your SLOWEST player when the team is full.
best starts at 0 and never needs a negative floor, because both speeds and
efficiencies are at least 1, so every rating is positive. A team of size 0 is
not allowed, and the loop never produces one.
Ties in efficiency are harmless. If two players share an efficiency, the second of them is examined with the first already in the heap, which is exactly the team the argument above needs.
## Overflow
Total speed reaches 10^5 * 10^5 = 10^10 on its own, and multiplying by an
efficiency of 10^5 gives 10^15. Both are past 32 bits by a wide margin. Even
the small declared test with two players of speed 10^5 and efficiency 10^5
lands on 2 * 10^10, which a 32-bit build reports as 1410065408. The running
total and the product both need 64 bits; 10^15 is comfortably inside the
signed 64-bit limit of about 9.2 * 10^18.
## Related problems
Problem #869 keeps the k nearest points in a bounded heap, which is the
same eviction rule with a fixed key. What is new here is that the key is not
given: the sort order and the heap order are DIFFERENT quantities, efficiency
and speed, and getting them the right way round is the problem.
## Cost
Time O(n log n). Space O(n).
Constraints - `1 ≤ k ≤ n ≤ 100000` - `1 ≤ speed ≤ 100000` - `1 ≤ efficiency ≤ 100000`
Input
The first line contains two integers n and k.
The second line contains n speeds.
The third line contains n efficiencies, in the same player order.
Output
Print one integer on its own line: the largest rating achievable by any team of between one and k players. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.