Naughty Stone Piles

题意翻译

在你的面前有 $n$ 堆石子从左往右排成一排，初始时每堆石子的大小（石子个数）依次为 $a_1, a_2, \ldots, a_n$。 你需要将这些石子进行合并。 每一步操作，你可以选择一堆石子并将这堆石子加入到另一堆石子中。如果你将第 $i$ 堆石子加入到第 $j$ 堆石子中，则第 $j$ 堆石子的大小将会增加第 $i$ 堆石子的大小，同时第 $i$ 堆石子将会消失 $\Rightarrow$ 我们将这样一步操作称为：将第 $i$ 堆石子合并到第 $j$ 堆石子中，其对应的代价为合并前第 $i$ 堆石子的大小。 你的任务是确定将所有石子合并成一堆所需的最小代价。 但是本题中有一个限制：对于任意一堆石子，你将其它石子合并到这堆石子的次数不能超过 $k$ 次。 有 $q$ 次询问，每次询问都会给出一个整数 $k$，你需要根据 $k$ 的值确定将 $n$ 堆石子合并成一堆的最小总代价（**注：可能存在几次询问的 $k$ 相同**）。

题目描述

There are $ n $ piles of stones of sizes $ a_{1},a_{2},...,a_{n} $ lying on the table in front of you. During one move you can take one pile and add it to the other. As you add pile $ i $ to pile $ j $ , the size of pile $ j $ increases by the current size of pile $ i $ , and pile $ i $ stops existing. The cost of the adding operation equals the size of the added pile. Your task is to determine the minimum cost at which you can gather all stones in one pile. To add some challenge, the stone piles built up conspiracy and decided that each pile will let you add to it not more than $ k $ times (after that it can only be added to another pile). Moreover, the piles decided to puzzle you completely and told you $ q $ variants (not necessarily distinct) of what $ k $ might equal. Your task is to find the minimum cost for each of $ q $ variants.

输入输出格式

输入格式

The first line contains integer $ n $ $ (1<=n<=10^{5}) $ — the number of stone piles. The second line contains $ n $ space-separated integers: $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{9}) $ — the initial sizes of the stone piles. The third line contains integer $ q $ $ (1<=q<=10^{5}) $ — the number of queries. The last line contains $ q $ space-separated integers $ k_{1},k_{2},...,k_{q} $ $ (1<=k_{i}<=10^{5}) $ — the values of number $ k $ for distinct queries. Note that numbers $ k_{i} $ can repeat.

输出格式

Print $ q $ whitespace-separated integers — the answers to the queries in the order, in which the queries are given in the input. Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

5
2 3 4 1 1
2
2 3

输出样例 #1

9 8 

说明

In the first sample one way to get the optimal answer goes like this: we add in turns the $ 4 $ -th and the $ 5 $ -th piles to the $ 2 $ -nd one; then we add the $ 1 $ -st pile to the $ 3 $ -rd one; we add the $ 2 $ -nd pile to the $ 3 $ -rd one. The first two operations cost $ 1 $ each; the third one costs $ 2 $ , the fourth one costs $ 5 $ (the size of the $ 2 $ -nd pile after the first two operations is not $ 3 $ , it already is $ 5 $ ). In the second sample you can add the $ 2 $ -nd pile to the $ 3 $ -rd one (the operations costs $ 3 $ ); then the $ 1 $ -st one to the $ 3 $ -th one (the cost is $ 2 $ ); then the $ 5 $ -th one to the $ 4 $ -th one (the costs is $ 1 $ ); and at last, the $ 4 $ -th one to the $ 3 $ -rd one (the cost is $ 2 $ ).