評価額が最大のものを 2 倍にし続けるのが最適です。

\(\max A_i\) を \(M\) と置きます。このとき、答えは \((\sum A_i - M) + M2^K\) となります。

\(2^K\) は繰り返し二乗法により \(O(\log K)\) で求めることができるので、\(O(N+\log K)\) で答えを求めることができます。

\(2^K\) は非常に巨大な値となりますが、適宜剰余を取りながら計算することで、全ての計算を 64bit 整数の範囲で行うことができます。

なお、C++では AtCoder Library を用いることで、pythonでは標準メソッドの pow を用いることで、べき剰余の計算が可能なため、明示的に繰り返し二乗法を実装する必要はありません。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint1000000007;

int main(){
  int n;
  long long k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  mint s = 0;
  for(int i=0; i<n; i++) s += a[i];
  mint m = *max_element(a.begin(), a.end());
  mint ans = (s - m) + m * mint(2).pow(k);
  cout << ans.val() << endl;
}

実装例 (Python)

MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A)
M = max(A)
ans = (S - M) + M * pow(2, K, MOD)
print(ans % MOD)