21843번 - Game Show 스페셜 저지다국어

Because of Covid-19 regulations, it is hard to film content that involves more than one location. Thus, Goosefilm Media decided to film a game show, where three teams compete in completing house chores for money. However, the show was rushed and rules were not thought through very well.

In this game show, three teams are given a choice of 3 × N chores to undertake. Each team has a certain probability of successfully completing each chore, and since the teams know each other very well, each team knows all probabilities for every team. The show proceeds as follows – the first team chooses N chores that it will be doing among all 3 × N chores, then the second team chooses N chores from the remaining 2×N chores, and the third team gets the N chores that were not taken by each of the previous teams. Then the teams proceed with doing chores in a mansion full of cameras. Once the time runs out, each team will be awarded $1000 for each chore it has completed, minus $1000 times the average number of chores completed by the 3 teams. If a team has completed fewer chores than the average, their award is negative, so they must pay that amount to the organizers of the game show.

Team number one hopes to do well, so they decided to pick N chores in a way that maximizes their expected award. Team 2, on the other hand, is upset by these stupid rules, so they decided to pick their N chores in a way that minimizes the expected reward of the first team (and in some cases makes them pay). Team 3 cannot choose anything, but they will diligently apply their best effort on their chores. Under these conditions, what is the expected award/fine of the first team? Before the start of the contest, the first team found out that team 2 is going to undermine them with their choices, so they will take it into account.

The first line of input contains one integer N – the number of chores per team, with 1 ≤ N ≤ 50 000. The next 3 lines each contain 3 × N numbers – the probability of completing each of the 3 × N chores by the first team on the first line, the second team on the second line, and the third team on the third line.

Each probability in the input is a floating-point number between 0 and 1 (inclusive).

Print one number – the expected reward of the first team. It will be considered correct if it differs from the jury’s answer by less than 10⁻⁶.

Even though the first team has the lowest probability to complete the first chore among the 3 options, in the optimal solution they should pick it (otherwise, team 2 or 3 will complete it for sure).