P10332 [UESTCPC 2024] One Stand to the End

Suppose you are Li Hua, a student at University of Electronic Science and Technology of China. In an episode of “One Stand to the End” in the year 4202, you participate as a contestant in the recording of the show. Unlike the rules from more than 2000 years ago, the show will not have stages where contestants duel in pairs and compete to buzz in or take turns answering. Instead, each contestant answers questions in a solo format. The specific rules are as follows. Before your answering stage begins, the system will draw $n$ questions from the question bank. Each question has a score $a_i$ based on its difficulty. The host will announce all question statements and their scores at the beginning, and then your answering stage starts. To make the show more interesting, during the answering stage, you cannot choose the order of questions freely. Specifically, except for Question $1$, every other question has **exactly one** prerequisite question. You can answer a question only after you have correctly answered its prerequisite. The production team guarantees that the prerequisite question index of Question $i$ is always less than $i$. In addition, if you submit a wrong answer when answering a question, the floor beneath you will open immediately, you will fall, and your answering stage ends. The sum of the scores of all previously answered correctly questions is your final score. If you answer all questions correctly, then the sum of the scores of all questions is your final score. Now you have read all the questions. Based on your knowledge, you estimate the probability $p_i$ that you will answer each question correctly. You need to design the best problem-solving strategy in the shortest time to maximize your expected score. Please output this score, ~~and write an English essay of at least 120 words about the experience of participating in this show~~.

The first line contains a positive integer $n$ $(2\le n\le 10^5)$, representing the number of questions. The next line contains $n$ positive integers $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^6)$, where $a_i$ is the score of Question $i$. The next line contains $n$ real numbers $p_1,p_2,\ldots,p_n$ $(0

Output one real number, representing the expected score under the optimal strategy. Suppose your output is $a$ and the correct answer is $b$. Your answer will be considered correct if and only if $\frac{|a-b|}{\max(1,b)}\le 10^{-9}$.

In the sample, the questions with higher scores also have higher probabilities of being answered correctly, so it is clearly optimal to answer in the order $1,2,3,4,5$. Translated by ChatGPT 5