QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

#21706. 【NOIP Round #4】水果

Statistics

题目描述

你在超市里工作。

超市里有 $n$ 个水果,第 $i$ 个水果的美味度为 $i$ ,价格为 $c_i$ ,并且保证 $c_i$ 单调不降。

现在要把这 $n$ 个水果摆成一排放到货架上,第 $j$ 个位置摆的水果是 $a_j$ 。但是你还没想好摆的顺序,所以可能会有 $a_j=-1$ ,表示这个位置摆的水果未定。

在你决定了摆放顺序之后,一位顾客进来买水果。他会从第一个位置开始往后走,每当遇到一个美味度比之前都要高的水果时就会把它买下,直到看完第 $k$ 个位置后离开。

你希望选择一个最优的摆放顺序,使得这位顾客出的钱最多。

但是你并不知道 $k$ 是多少,因此你希望对每个 $k$ 都求出答案。你对不同的 $k$ 给出的顺序可以不同。

输入格式

第一行一个正整数 $n$ 。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 。

第三行 $n$ 个正整数 $c_1,c_2,\cdots,c_n$ 。

输出格式

输出一行 $n$ 个正整数,表示 $k=1,2,\cdots,n$ 时的答案。

样例一

input

5
-1 3 -1 -1 -1
1 2 2 2 3

output

3 4 7 9 9

explanation

  • $k=1$ 的最优方案是把第 $5$ 个水果放第一个位置,即令 $a_1=5$ ,后面任意。
  • $k=2$ 的最优方案是令 $a_1=2$ 。
  • $k=3$ 的最优方案是令 $a_1=2,a_3=5$ 。
  • $k=4$ 的最优方案是令 $a_1=2,a_3=4,a_4=5$ 。
  • $k=5$ 的最优方案是令 $a_1=2,a_3=4,a_4=5,a_5=1$ 。

样例二

input

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

output

1 2 3 4 5 6 6 7 8 9 9 9 9

样例三

input

10
-1 -1 -1 -1 5 -1 -1 -1 9 -1
5 11 24 27 35 60 72 81 91 92

output

92 173 245 305 305 332 356 367 406 498

样例四、五、六

见下发文件。

数据范围

本题采用子任务捆绑测试。

对于所有数据,保证 $1\le n\le 4\times 10^5, -1\le a_i\le n, a_i\ne 0, 1\le c_i\le 10^9$ ,$a$ 中不存在两个相同的正整数,$c$ 单调不降。

子任务编号 特殊性质 分值
$1$ $n\le 8$ $10$
$2$ $a_1=a_2=\cdots=a_n=-1$ $10$
$3$ $n\le 200$ $20$
$4$ $n\le 2000$ $20$
$5$ $c_1=c_2=\cdots=c_n=1$ $20$
$6$ $ $ $20$

时间限制:$\texttt{3s}$

空间限制:$\texttt{1024MB}$

提示

pjudge 缺投。