All submissions for this problem are available.
It's placement time at IISc! All students are busy studying for interiews and preparing their resumes. Lalit is also appearing for the placements. He has made a list of all companies along with their salaries, in the order of their date for placement(i.e the order in which the companies are going to come for placements,the salaries can be totally random). Being more mathematically oriented, he has also compiled the probabilities of his getting selected by each company. The placement process is as follows. Any student can write as many companies as he wants, as long as he is not selected by any company. Once he is selected by some company, his placement ends, and he cannot write any more companies. Lalit wants to devise a strategy such that he would write only those companies such that his expected salary is high. His strategy should take into consideration his chances of getting into a particular company and whether it is safe to not sit for a company in case he wishes to apply for a higher paying company. You must help Lalit decide which companies he should write, and which he shouldn't, in order to get the highest expected salary.
The first line of input contains 'T', the number of test cases (1<=T<=1000). This is followed by T test cases. Each test case consists of a blank line followed by three lines. The first line contains a single number 'N', the number of companies (1 <= N <= 100000). The next line consists of 'N' integers separated by spaces, which are the salaries of the companies, in order. The third line consists of 'N' floating point numbers separated by spaces, which are the probabilities of Pratik's getting selected by the companies, in order.
The output should consist of 'T' lines corresponding to the 'T' test cases. Each line should contain one floating point number, accurate to 6 decimal places, which is the best expected salary.
Input: 2 2 10000 20000 0.5 0.3 3 40000 10000 20000 0.6 0.3 0.8 Output: 8000.000000 30400.000000
|Time Limit:||1.29 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, D, PERL, FORT, ADA, ASM, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, TCL, PERL6, CLOJ, FS|
Fetching successful submissions