P8726 [Lanqiao Cup 2020 NOI Qualifier AB3] Traveler

Long ago, there were $n$ islands on the sea, numbered from $1$ to $n$. The residents were troubled by ocean currents and could not reach any island with a smaller number than the island they were currently on. After several years, the population on the islands increased with the island number (ties are allowed). As an excellent traveler (an $\mathrm{RP}$ scholar), you want to start a trip from island $1$ to gain more $\mathrm{RP}$. Due to the ocean currents, you can only travel to islands with a larger number than your current island. Because you are kind, when you leave an island you will distribute your $\mathrm{RP}$ to the residents. Specifically, your $\mathrm{RP}$ will be divided by $2$ and rounded down (i.e., truncated toward zero). (When your $\mathrm{RP}$ is negative, the residents still have to share the burden, because you have built a deep friendship.) Island $i$ has $T_i$ people. However, you are picky: each time you travel from island $j$ to island $i$, you will only do $T_i \times T_j$ good deeds on the island you arrive at. (Each good deed gives $1$ point of $\mathrm{RP}$.) The only downside is that staying on an island costs a lot. Staying on island $i$ deducts $F_i$ points of $\mathrm{RP}$. Note: When leaving an island, first halve your $\mathrm{RP}$, then deduct the lodging $\mathrm{RP}$ cost, and finally do good deeds on the newly arrived island to increase $\mathrm{RP}$. When leaving island $1$, you must deduct the lodging cost on island $1$. When you arrive at the last island of your trip, you must finish doing the good deeds before the trip ends; that is, you do not need to deduct the lodging cost on the final island you arrive at. You love traveling ($\mathrm{RP}$), so you start from island $1$. Initially you have $0$ points of $\mathrm{RP}$. You want to choose some islands to visit and finally stop at one island. Find the maximum possible $\mathrm{RP}$ value.

The first line contains an integer $n$, the total number of islands. The second line contains $n$ integers $T_1, T_2, \cdots, T_n$, the population of each island. The third line contains $n$ integers $F_1, F_2, \cdots, F_n$, the $\mathrm{RP}$ loss for lodging on each island.

Output one number, the maximum $\mathrm{RP}$ value you can obtain.

**Sample Explanation** Going directly from island $1$ to island $3$ is optimal. Starting with $0$ points of $\mathrm{RP}$, halving and truncating still gives $0$. Deduct $1 \mathrm{RP}$ for lodging on island $1$. On island $3$, doing good deeds produces $4 \times 5 = 20$ points of $\mathrm{RP}$. Finally you get $19$ points of $R P$. **Constraints and Notes** For $20\%$ of the testdata, $1 \leq n \leq 15$. For $70\%$ of the testdata, $1 \leq n \leq 5000$. For all testdata, $1 \leq n \leq 5 \times 10^5$, $1 \leq T_i \leq 20000$, $1 \leq F_i \leq 2 \times 10^8$. The given $T_i$ are already sorted in nondecreasing order. It is recommended to use 64-bit signed integers for calculations. Lanqiao Cup 2020, Round 3 Provincial Contest, AB Group, Problem J. Upd.2024.7.13 Hack data has been added. Translated by ChatGPT 5