UOJ Logo

NOI.AC

#83. 排列

统计

题目描述

老虎和蒜头是好朋友。

老虎最近购置了一个扫地机器人,同时为了让机器人扫地变得美观,老虎将他家的地板划分成了 $ 1 \times n $ 的小块,并在每一块地面上都加装了五颜六色的灯。当机器人第一次移动到第 $ i $ 块地板上时,第 $ i $ 块地板上的灯将被点亮。显然,机器人只能左右移动而不能跳跃,因此每次机器人只能从第 $ i $ 块地板移动到 $ i - 1 $ 或 $ i + 1 $ 。

蒜头觉得美观度不能量化真是无趣,因此他定义了点亮顺序 $ \{ P_1, P_2, \ldots, P_n \} $ ,其中 $ P_i $ 表示第 $ i $ 个点亮的灯所在的地板编号。随后,他又定义了点亮顺序 $ P $ 的美观度 $ f(P) = \sum_{i = 1}^n D_i \times [P_{C_i} = i] $ ,即如果第 $ i $ 盏灯被第 $ C_i $ 个点亮便会产生 $ D_i $ 的美观度。

现在蒜头想要知道,如果一开始机器人被投放在 $ i $ 位置,所有移动方案中能产生的最大美观度是多少。

输入格式

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

接下来一行 $ n $ 个正整数 $ C_i $ ,注意 $ C_i $ 可能重复。

接下来一行 $ n $ 个正整数 $ D_i $ 。

输出格式

共输出一行 $ n $ 个正整数,第 $ i $ 个数表示一开始投放在 $ i $ 时产生的最大美观度。

样例数据

样例一

input

5
1 3 3 1 3
4 3 1 2 10

output

5 1 10 12 1

explanation

当一开始投放在 $ 1 $ 时,最优情况下 $P = \{1,2,3,4,5\}$ ,产生的最大美观度为 $ 5 $ 。

当一开始投放在 $ 2 $ 时,最优情况下 $P = \{2,1,3,4,5\}$ ,产生的最大美观度为 $ 1 $ 。

当一开始投放在 $ 3 $ 时,最优情况下 $P = \{3,4,5,2,1\}$ ,产生的最大美观度为 $ 10 $ 。

当一开始投放在 $ 4 $ 时,最优情况下 $P = \{4,3,5,2,1\}$ ,产生的最大美观度为 $ 12 $ 。

当一开始投放在 $ 5 $ 时,最优情况下 $P = \{5,4,3,2,1\}$ ,产生的最大美观度为 $ 1 $ 。

数据范围及限制

对于 100% 的数据,$ 1 \le C_i \le n \le 3 \times 10^5, 1 \le D_i \le 10^9 $ 。

对于 25% 的数据,$ n \le 300 $ 。

对于 50% 的数据,$ n \le 5000 $ 。

对于 75% 的数据,$ n \le 50000 $ 。

时间限制: 1s

空间限制: 512MB