/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の株式銘柄に投資しています。i 番目の銘柄の現在の評価額は L_i 円です。
高橋君はこれから K 回の投資チャンスを順番に使います。各回では、N 個の銘柄から好きな銘柄を 1 つ選び、その銘柄の現在の評価額を 2 倍にします。このとき、同じ銘柄を複数回選ぶこともできます。
K 回の投資チャンスをすべて使い終えた後の、N 個の銘柄の評価額の合計が最大となるように各回の銘柄を選ぶとき、その最大値を求めてください。
答えは非常に大きくなる可能性があるため、最大値を 10^9 + 7 で割った余りを出力してください。ただし、余りを取る操作は最大値を求めた後に行うものとします。すなわち、途中で余りを取った結果に基づいて大小を比較するのではなく、真の値としての最大値を求めたうえで、その値を 10^9 + 7 で割った余りを出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq L_i \leq 10^9
- 入力はすべて整数である。
入力
N K L_1 L_2 \ldots L_N
- 1 行目には、銘柄の数を表す整数 N と、投資チャンスの回数を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各銘柄の現在の評価額を表す整数 L_1, L_2, \ldots, L_N が、スペース区切りで与えられる。
出力
K 回の投資チャンスをすべて使い終えた後の評価額の合計の最大値を 10^9 + 7 で割った余りを、1 行で出力せよ。
入力例 1
3 2 3 1 2
出力例 1
15
入力例 2
5 10 4 8 2 5 1
出力例 2
8204
入力例 3
4 1000000000000000000 1000000000 999999999 999999998 999999997
出力例 3
963666195
Score : 366 pts
Problem Statement
Takahashi is investing in N stock issues. The current valuation of the i-th stock is L_i yen.
Takahashi will use K investment chances one by one in order. In each chance, he chooses any one of the N stocks and doubles its current valuation. He may choose the same stock multiple times.
Determine the maximum possible total valuation of all N stocks after all K investment chances have been used, when he chooses the stock in each chance to maximize this total.
Since the answer can be extremely large, output the maximum value modulo 10^9 + 7. Note that the modulo operation is applied only after determining the true maximum value. That is, you should not compare values based on intermediate results taken modulo 10^9 + 7; instead, find the maximum value as a true (unmodded) number, and then output that value modulo 10^9 + 7.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq L_i \leq 10^9
- All input values are integers.
Input
N K L_1 L_2 \ldots L_N
- The first line contains an integer N representing the number of stocks and an integer K representing the number of investment chances, separated by a space.
- The second line contains integers L_1, L_2, \ldots, L_N representing the current valuations of each stock, separated by spaces.
Output
Output in one line the maximum total valuation after all K investment chances have been used, modulo 10^9 + 7.
Sample Input 1
3 2 3 1 2
Sample Output 1
15
Sample Input 2
5 10 4 8 2 5 1
Sample Output 2
8204
Sample Input 3
4 1000000000000000000 1000000000 999999999 999999998 999999997
Sample Output 3
963666195