P11274 "Diligent-OI R1 D" DlgtTemplate

A chessboard is made of wooden boards. This problem is about a chessboard, so...

There is a chessboard with $1$ row and $n$ cells, numbered $1\sim n$. Each cell has a score $a_i$ written on it. Now you need to choose some cells **from left to right** in order; you may also choose none. After choosing some cells, certain cells will clear the earliest $b_i$ cells among the currently chosen cells, turning them into unchosen cells, but you **cannot** go back and choose those cells again. In particular, if the number of chosen cells before this cell is less than $b_i$, then this cell and the cells after it **will not** be cleared into unchosen cells. Please find a left-to-right choosing plan that maximizes the sum of scores of the chosen cells.

The first line contains $n$, meaning the chessboard has $n$ cells. The next line contains $n$ integers, representing the scores $a_1\sim a_n$ for cells $1\sim n$. The next line contains $n$ non-negative integers, representing the clearing counts $b_1\sim b_n$ for cells $1\sim n$.

You need to output a specific plan. The first line outputs a non-negative integer $k$, meaning you chose $k$ cells. The second line outputs $k$ positive integers in increasing order, meaning the indices of the cells you chose from left to right. If you choose no cells, output an empty line. The third line outputs $ans$, meaning your final answer. Ns6 is very kind. If you cannot output the plan but your answer is correct, you can still get $40\%$ of the points. But in this case, you still need to output $k$ and the $k$ positive integers in increasing order.

#### [Sample #1 Explanation] First choose the first number $1$. Although $b_1=1$, since there are no chosen numbers before it, it will not clear anything. Then choose the second number $1$. Since $b_2=0$, it will not clear anything. Then choose the third number $4$. Since $b_3=0$, it will not clear anything. Then choose the fourth number $5$. Since $b_4=2$, the first and second chosen numbers will be cleared into unchosen numbers. At this time, the answer is $4+5=9$. The method is not unique. #### [Constraints and Notes] For $100\%$ of the testdata, $1\le n\le3000$, $|a_i|\le10^8$, $0\le b_i\le n$. | Subtask ID | $n\le$ | Special Property | Points | | :----------: | :----------: | :----------: | :----------: | | $0$ | $20$ | None | $25$ | | $1$ | $500$ | None | $20$ | | $2$ | $3000$ | $b_i>0$ | $5$ | | $3$ | $3000$ | $b_i=0$ | $5$ | | $4$ | $3000$ | $a_i=1$ | $15$ | | $5$ | $3000$ | None | $30$ | Translated by ChatGPT 5