305229: CF994B. Knights of a Polygonal Table
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Knights of a Polygonal Table
题意翻译
## 题目描述 有 $n$ 个骑士想决战。每个骑士都有能力值,且身上带有一些金币。如果骑士 $A$ 的能力值大于骑士 $B$ ,那么骑士 $A$ 就可以杀死骑士 $B$ ,并获得骑士 $B$ 身上的所有金币。但就算是骑士也不会残忍过度,他们最多只会杀死 $k$ 个骑士。对于每一位骑士,请你求出在决战后他身上金币的最大值。 ## 输入格式 第 $1$ 行,有 $2$ 个整数,分别为骑士人数 $n$ 和杀人数上限 $k$ 。 (数据范围: $1 \leqslant n \leqslant 10^{5}$ , $0 \leqslant k \leqslant min(n - 1,\ 10)$ ) 第 $2$ 行,有 $n$ 个整数,表示每个骑士的能力值 $p_i$ 。 第 $3$ 行,有 $n$ 个整数,表示每个骑士原有的金币 $c_i$ 。 (数据范围: $1 \leqslant p_i \leqslant 10^{9}$ , $0 \leqslant c_i \leqslant 10^{9}$ ) ##输出格式 $1$ 行内输出 $n$ 个整数,决战后每个骑士身上金币的最大值,每两个数间以单个空格隔开。 ##提示与说明 - 第 $1$ 组样例的解释: 第 $1$ 个骑士是最蒻的,因此他谁也不能杀,只能保留自己原有的金币。 第 $2$ 个骑士只能杀死第 $1$ 个骑士,因此他最多拥有 $2 + 1 = 3$ 个金币。 第 $3$ 个骑士是最蔃的,但他只能选择杀 $k = 2$ 个骑士。显然他会杀死第 $2$ 个骑士和 第 $4$ 个骑士,因为他们身上的金币更多。因此他最多拥有 $11 + 2 + 33 = 46$ 个金币。 第 $4$ 个骑士应该杀死第 $1$ 个和第 $2$ 个骑士,因此他最多拥有 $33 + 1 + 2 = 36$ 个金币。 - 第 $2$ 组样例的解释: 除了最蒻的第 $1$ 个骑士谁也不能杀,其他骑士都能杀死前一个骑士并获得他的金币。 - 第 $3$ 组样例的解释: 由于只有一个骑士在决战中,他无法杀死任何人。 感谢@Sooke 提供翻译题目描述
Unlike Knights of a Round Table, Knights of a Polygonal Table deprived of nobility and happy to kill each other. But each knight has some power and a knight can kill another knight if and only if his power is greater than the power of victim. However, even such a knight will torment his conscience, so he can kill no more than $ k $ other knights. Also, each knight has some number of coins. After a kill, a knight can pick up all victim's coins. Now each knight ponders: how many coins he can have if only he kills other knights? You should answer this question for each knight.输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ $ (1 \le n \le 10^5, 0 \le k \le \min(n-1,10)) $ — the number of knights and the number $ k $ from the statement. The second line contains $ n $ integers $ p_1, p_2 ,\ldots,p_n $ $ (1 \le p_i \le 10^9) $ — powers of the knights. All $ p_i $ are distinct. The third line contains $ n $ integers $ c_1, c_2 ,\ldots,c_n $ $ (0 \le c_i \le 10^9) $ — the number of coins each knight has.
输出格式
Print $ n $ integers — the maximum number of coins each knight can have it only he kills other knights.
输入输出样例
输入样例 #1
4 2
4 5 9 7
1 2 11 33
输出样例 #1
1 3 46 36
输入样例 #2
5 1
1 2 3 4 5
1 2 3 4 5
输出样例 #2
1 3 5 7 9
输入样例 #3
1 0
2
3
输出样例 #3
3