| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 80 | 14 | 4 | 36.364% |
Supermarkets usually have fruits for sale in sections, where each section is dedicated to a single type of fruit. The supermarket that Benson the Rabbit is visiting has $N$ sections and $N$ types of fruits. The sections are numbered from 1ドル$ to $N$ and each fruit is numbered from 1ドル$ to $N$.
The $i$th fruit has tastiness $i$ and cost $C_i$. It is guaranteed that $C_i ≤ C_j$ for all 1ドル ≤ i < j ≤ N$.
Each of the $N$ sections is to be assigned a distinct type of fruit. At the moment, the type of fruit assigned to section $j$ is $A_j$. If $A_j = -1,ドル then section $j$ is empty. Otherwise, fruit $A_j$ is already assigned to section $j$. Once all $N$ fruits have been assigned, the supermarket will open and Benson will enter the supermarket to buy the fruits.
Benson is very picky but also in a rush, so he will visit the sections in increasing order. Benson’s basket is initially empty, and when he reaches a section, he will compare the tastiness of the fruit in that section to the tastiness of all of the fruits in his basket. If his basket is empty, or if the tastiness of the fruit at the current section is greater than the tastiness of every other fruit in his basket, Benson will add that fruit to his basket.
To maximise revenue, you have been tasked with assigning the fruits to the sections such that the sum of cost of fruits that Benson adds to his basket is maximised. As Benson is rushing for time, he might only visit the first few sections before going straight to the cashier. Help compute, for each $k$ from 1ドル$ to $N,ドル the maximum possible revenue that can be achieved if Benson only visits the first $k$ sections given that the arrangement of fruits can change for different $k$.
Your program must read from standard input.
The input starts with a line with one positive integer $N$.
The second line contains $N$ integers where the ith integer represents $A_i$.
The third line contains $N$ integers where the ith integer represents $C_i$.
Your program must print to standard output.
The output should contain a $N$ integers on a single line. The kth one should be the maximum sum of costs that Benson will pay if the fruits are assigned optimally if he visits only the first $k$ sections.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $N ≤ 8$ |
| 2 | 5 | $A_j = -1$ for all 0ドル ≤ j < n$ |
| 3 | 11 | $N ≤ 200$ |
| 4 | 13 | $N ≤ 2000$ |
| 5 | 23 | $C_i = 1$ for all 0ドル ≤ i < n$ |
| 6 | 42 | - |
5 -1 -1 -1 -1 -1 1 1 1 1 1
1 2 3 4 5
We can arrange the fruits in increasing order $(1,2,3,4,5)$. Benson will take all fruits that he passes by, so for each $k$ from 1ドル$ to 5ドル,ドル Benson will take $k$ fruits which have a total cost of $k$.
This testcase is valid for all subtasks.
5 -1 3 -1 -1 -1 1 2 2 2 3
3 4 7 9 9
If Benson only visits the first section, it is optimal to put fruit 5ドル$ in section 1ドル$. This gives a cost of 3ドル$.
If Benson only visits the first 2ドル$ sections, it is optimal to put fruit 2ドル$ in section 1ドル$ and fruit 3ドル$ in section 2ドル$. This gives a cost of 2ドル + 2 = 4$.
If Benson only visits the first 3ドル$ sections, it is optimal to put fruit 2ドル$ in section 1ドル$ and fruit 3ドル$ in section 2ドル$ and fruit 5ドル$ in section 3ドル$. This gives a cost of 2ドル + 2 + 3 = 7$.
If Benson visits either the first 4ドル$ or all 5ドル$ sections, it is optimal to put the fruits in the order 2ドル,ドル 3ドル,ドル 4ドル,ドル 5ドル,ドル 1ドル$. This gives a cost of 2ドル + 2 + 2 + 3 = 9$.
This testcase is valid for subtasks 1, 3, 4 and 6.
13 -1 -1 5 6 -1 -1 7 11 -1 -1 10 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 6 7 8 9 9 9 9
This testcase is valid for subtasks 3, 4, 5 and 6.
10 -1 -1 -1 -1 5 -1 -1 -1 9 -1 5 11 24 27 35 60 72 81 91 92
92 173 245 305 305 332 356 367 406 498
This testcase is valid for subtasks 3, 4 and 6.