P15800 [GESP202603 Level 6] Number Selection

Related multiple-choice and true/false questions: .

Given two arrays $a=[a_1,\dots,a_n]$ and $b=[b_1,\dots,b_n]$, each containing $n$ integers. You need to choose some indices $p_1< \cdots< p_k$ ($1\leq k\leq n$) such that the following conditions are satisfied: - $1\leq p_i\leq n$ ($1\leq i\leq k$). - $p_{i+1}\geq p_i+b_{p_i}$ ($1\leq i< k$). Under these conditions, you need to maximize $\sum_{i=1}^k a_{p_i}$, i.e., maximize the sum of the values in array $a$ at the chosen indices.

The first line contains a positive integer $n$, indicating the array length. The second line contains $n$ positive integers $a_1,a_2,\dots,a_n$, representing array $a$. The third line contains $n$ positive integers $b_1,b_2,\dots,b_n$, representing array $b$.

One line containing an integer, representing the maximum possible sum of the values in array $a$ at the chosen indices, under the index constraints.

For $40\%$ of the testdata, it is guaranteed that $2\leq n\leq 10^3$. For all testdata, it is guaranteed that $2\leq n\leq 10^5$, $0\leq a_i\leq 10^9$, and $0\leq b_i\leq n$. Translated by ChatGPT 5