Triway Cup '19 Summer B - Cameras

View as PDF

Submit solution

Points: 5
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem types

You have won the labour lottery and are now an apartment manager at 100 KRUSHVICE st. There, your job is to ensure that the N tenants are satisfied, and more important, following the government directives.

In order to do the latter, you plan to install K_i cameras in tenant i's room. Camera j in the i^\text{th} person's room has a probability of P_{i,j} of discovering that person doing something illegal. (Note that discovering a person twice has no additional effect). However, due to budget cuts, your number of cameras is limited to C. Determine the maximum expected number of people caught doing something illegal if you only install up to C cameras, for ALL values of C from 1 to \sum_{i=0}^{N-1} K_i.

Constraints

1 \le N \le 5 \times 10^5

\sum_{i=0}^{N-1} K_i \le 5 \times 10^5

The probability P_{i,j} is a real number between 0 and 1.

Input Specification

Line 1: An integer, N, the number of tenants.
Next N lines: An integer K_i, the number of cameras planned to be installed in the i^\text{th} person room, and K real numbers, the values of P_{i,j}.

Output Specification

\sum_{i=0}^{N-1} K_i lines, each with a single real number, the maximum expected value after installing C (1 \le C \le \sum_{i=0}^{N-1} K_i) cameras. Your answer will be accepted if it differs from the expected answer by up to 10^{-6}.

Sample Input

3
3 0.5 0.5 0.5
2 0.4 0.25
1 0.3

Sample Output

0.50000000
0.90000000
1.20000000
1.45000000
1.60000000
1.72500000

Also note that

0.50000000
0.90000000
1.20000000
1.44999999
1.60000000
1.72500001

is also a valid output, for example.


Comments

There are no comments at the moment.