Compute Power
Contest: Codeforces Round 488 by NEAR (Div. 1)
Difficulty rating: 2500
Tags: binary search, dp, greedy

You need to execute several tasks, each associated with number of processors it needs, and the compute power it will consume.

You have sufficient number of analog computers, each with enough processors for any task. Each computer can execute up to one task at a time, and no more than two tasks total. The first task can be any, the second task on each computer must use strictly less power than the first. You will assign between 1 and 2 tasks to each computer. You will then first execute the first task on each computer, wait for all of them to complete, and then execute the second task on each computer that has two tasks assigned.

If the average compute power per utilized processor (the sum of all consumed powers for all tasks presently running divided by the number of utilized processors) across all computers exceeds some unknown threshold during the execution of the first tasks, the entire system will blow up. There is no restriction on the second tasks execution. Find the lowest threshold for which it is possible.

Due to the specifics of the task, you need to print the answer multiplied by 1000 and rounded up.

Input format:
The first line contains a single integer n (1 ≤ n ≤ 50) — the number of tasks.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 108), where ai represents the amount of power required for the i-th task.

The third line contains n integers b1, b2, ..., bn (1 ≤ bi ≤ 100), where bi is the number of processors that i-th task will utilize.

Output format:
Print a single integer value — the lowest threshold for which it is possible to assign all tasks in such a way that the system will not blow up after the first round of computation, multiplied by 1000 and rounded up.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example the best strategy is to run each task on a separate computer, getting average compute per processor during the first round equal to 9.

In the second task it is best to run tasks with compute 10 and 9 on one computer, tasks with compute 10 and 8 on another, and tasks with compute 9 and 8 on the last, averaging (10 + 10 + 9) / (10 + 10 + 5) = 1.16 compute power per processor during the first round.

Example input:
6
8 10 9 9 8 10
1 1 1 1 1 1

Example output:
9000

Example input:
6
8 10 9 9 8 10
1 10 5 5 1 10

Example output:
1160

Editorial:
First observe that if for some threshold there's a way to assign tasks in a way that they will finish computation, it is also possible for all higher thresholds.
Because of that, we can use binary search to find the threshold. Now the problem is reduced to figuring out if for a given threshold the tasks can be assigned in a way that the system doesn't blow up too early.
For that, observe that if the average power per processor exceeds a given threshold, it also means that the average power exceeds the threshold multiplied by the number of processors, which in turn means that the average power minus threshold multiplied by the number of processors exceeds 0. By regrouping summands, we can associate the value (power - threshold * num_of_processors) to each task, and reduce the problem to finding the mapping of tasks to computers that minimizes the sum of values of all the tasks assigned as the first task, and compare it to zero.
To do that, we can use sort the tasks by the power value in decreasing order and use dynamic programming. The dimensions are:
i: The current task considered
j: How many tasks that use strictly more power than the i - 1st task are assigned as the first task to some computer that doesn't have a second task yet.
k: How many tasks that use exactly as much power as the i - 1st task are assigned as the first task to some computer that doesn't have a second task yet.
Transitions involve either assigning the task as a first task to some computer that has no tasks yet (increasing k, increasing the value by the value of the i-th task) or assigning the task to some computer that has a first task (decreasing j, not changing the value). Whenever i-th task's power differs from i - 1st task, j increases by k, and k becomes equal to zero.
The minimal sum of task values is then equal to the minimum of dp[n][j][k] over all j, k. Update the state of the binary search depending on whether the minimal sum is greater than zero or not.
Note that this is O(n3) × log(precision). As an exercise, find a solution that is O(n2) × log(precision)