#P17738. 水果
水果
题目描述
你在超市里工作。
超市里有 个水果,第 个水果的美味度为 ,价格为 ,并且保证 单调不降。
现在要把这 个水果摆成一排放到货架上,第 个位置摆的水果是 。但是你还没想好摆的顺序,所以可能会有 ,表示这个位置摆的水果未定。
在你决定了摆放顺序之后,一位顾客进来买水果。他会从第一个位置开始往后走,每当遇到一个美味度比之前都要高的水果时就会把它买下,直到看完第 个位置后离开。
你希望选择一个最优的摆放顺序,使得这位顾客出的钱最多。
但是你并不知道 是多少,因此你希望对每个 都求出答案。你对不同的 给出的顺序可以不同。
输入格式
第一行一个正整数 。
第二行 个整数 。
第三行 个正整数 。
输出格式
输出一行 个正整数,表示 时的答案。
样例输入 1
5
-1 3 -1 -1 -1
1 2 2 2 3
样例输出 1
3 4 7 9 9
样例输入 2
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
样例输出 2
1 2 3 4 5 6 6 7 8 9 9 9 9
样例输入 3
10
-1 -1 -1 -1 5 -1 -1 -1 9 -1
5 11 24 27 35 60 72 81 91 92
样例输出 3
92 173 245 305 305 332 356 367 406 498
样例解释 1
- 的最优方案是把第 个水果放第一个位置,即令 ,后面任意。
- 的最优方案是令 。
- 的最优方案是令 。
- 的最优方案是令 。
- 的最优方案是令 。
测试点约束
对于所有数据,保证 ,,,, 中不存在两个相同的正整数, 单调不降。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| 1 | 10 | |
| 2 | ||
| 3 | 20 | |
| 4 | ||
| 5 | ||
| 6 | 无 |