この問題は \(M\) を全探索することで解くことができます。

次の問題を考えます。

整数 \(M\) を自由に選ぶ。その後、 \(K\) 人を選ぶ。

• 選んだ \(K\) 人の冒険者の攻撃力の合計を \(S\) とする
• 選んだ \(K\) 人の冒険者の防御力は全員 \(M\) 以上でなければならない
• パーティの戦闘力は \(S\times M\) である

パーティの戦闘力の最大値は？

この問題の答えは元の問題の答えと一致します。（\(K\) 人を選んでから \(M\) を決めるとすると、\(K\) 人の防御力の最小値を \(M\) としたときにパーティの戦闘力は最大となり、元の問題で定義されるパーティの戦闘力に一致する）

元の問題の代わりにこの問題を考えます。

\(M\) を決めたとき、選択可能な冒険者のうち攻撃力が高い方から \(K\) 人を選ぶのが最適であることは明らかです。また、 \(M\) を小さくするごとに選択可能な冒険者は単調に増加します。さらに、選択可能な冒険者の集合が変化するのは \(M\) が \(B\) に含まれるいずれかの値になったときに限ります。

よって、\(B\) の降順に冒険者を見ながら、「選択可能な冒険者の集合に冒険者を追加する」「選択可能な冒険者の集合から攻撃力が高い方 \(K\) 人の攻撃力の和を求める」ができれば十分です。これは、優先度付きキューを用いて「選択可能な冒険者のうち攻撃力が高い方から \(K\) 人」を管理することで、高速に処理することができます。（新たに選択可能になった冒険者をキューに追加し、人数超過分を攻撃力が低い順にキューから取り除く）

計算量は \(O(N\log N)\) となります。

C++ の優先度付きキューは値が大きなものを優先して返すため、値を -1 倍してからキューに入れることで、実質的に最小値を優先して取り出すキューとして扱っています。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<pair<int,int>>ba(n);
  for(int i=0; i<n; i++) cin >> ba[i].second >> ba[i].first;
  sort(ba.rbegin(), ba.rend());

  priority_queue<int>q;
  long long s = 0;
  for(int i=0; i<k; i++){
    int a = ba[i].second;
    q.push(-a);
    s += a;
  }

  long long ans = s * ba[k-1].first;
  for(int i=k; i<n; i++){
    auto[b, a] = ba[i];
    s += a;
    q.push(-a);
    s -= -q.top();
    q.pop();
    ans = max(ans, s * b);
  }
  cout << ans << endl;
}

実装例 (Python)

import heapq
N, K = map(int, input().split())
BA = []
for _ in range(N):
  a, b = map(int, input().split())
  BA.append((b, a))
BA.sort(reverse=True)

q = []
for _, a in BA[:K]:
  heapq.heappush(q, a)

s = sum(q)
ans = s * BA[K-1][0]

for b, a in BA[K:]:
  s += a
  s -= heapq.heappushpop(q, a)
  ans = max(ans, s * b)

print(ans)