乗るアトラクションの個数 \(X\) を決め打って、これを二分探索することを考えましょう。

乗るアトラクションの集合を決めてそれらすべてに搭乗完了するまでの時間を最小化する場合、 \(A_i - B_i\) が大きい順にファストパスを使うのが最適です。
このとき、アトラクションを \(A_i - B_i\) が大きい順にソートした列について、以下のような最適解が存在します。

• 以下の条件を満たす \(j\) が存在する。
  • 先頭 \(j\) 個のアトラクションの中から \(\min(X,K)\) 個のアトラクションを選択し、ファストパスを使って搭乗する。
  • 残り \(N-j\) 個のアトラクションの中から \(\max(X-K,0)\) 個のアトラクションを選択し、通常通り搭乗する。

以上の各項目に要する最小時間は、全ての \(j\) に対して priority_queue を用いて求めることができます。

これにより、この問題を時間計算量 \(O(N \log^2 N)\) で解くことができました。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pl=pair<long long,long long>;

bool comp(const pl &l, const pl &r){
  return (l.first-l.second) > (r.first-r.second);
}

int main(){
  long long n,k,t;
  cin >> n >> k >> t;
  vector<pl> a(n);
  for(long long i=0;i<n;i++){
    cin >> a[i].first >> a[i].second;
  }
  sort(a.begin(),a.end(),comp);

  long long l=1,r=n;
  while(l<=r){
    long long x=(l+r)/2;
    vector<long long> pre(n+1,4e18);
    vector<long long> suf(n+1,4e18);
    long long ps=min(x,k);
    long long ss=max(x-k,0ll);
    {
      long long sum=0;
      priority_queue<long long> pq;
      for(long long i=0;i<n;i++){
        sum+=a[i].second;
        pq.push(a[i].second);
        if(pq.size()>ps){
          long long od=pq.top(); pq.pop();
          sum-=od;
        }
        if(pq.size()==ps){pre[i]=sum;}
      }
    }
    
    {
      long long sum=0;
      priority_queue<long long> pq;
      if(ss==0){suf[n]=0;}
      for(long long i=n-1;i>=0;i--){
        sum+=a[i].first;
        pq.push(a[i].first);
        if(pq.size()>ss){
          long long od=pq.top(); pq.pop();
          sum-=od;
        }
        if(pq.size()==ss){suf[i]=sum;}
      }
    }

    long long tim=8e18;
    for(long long i=0;i<n;i++){
      tim=min(tim,pre[i]+suf[i+1]);
    }
    if(tim<=t){l=x+1;}
    else{r=x-1;}
  }
  cout << r << "\n";
  return 0;
}