Rice Cracker

2 secs 1024 MB

dyktr_06

Problem

Submissions

Test cases

Editorial

戦闘力を $K$ 以上にできるかという判定問題を考えます。

$A$ についてソートをしておくと、各 $i$ $(1 \leq i \leq N - 1)$ について、
スピードを $K$ 以上にするための $j$ $(i < j \leq N)$ を二分探索で求めることができます。

さらに、あらかじめ区間 max を計算しておくことにより、 $B$ についても $K$ 以上を達成できるかを判定することができます。

以上により、判定問題を $O(N \log N)$ で解くことができたので、
全体の計算量は $O(N \log N \log (\max A))$ となり、十分高速にこの問題を解くことができました。

実装例(C++)

#include <bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; i++){
    cin >> a[i] >> b[i];
  }
  vector<pair<int, int>> c(n);
  for(int i = 0; i < n; i++){
    c[i] = make_pair(a[i], b[i]);
  }
  sort(a.begin(), a.end());
  sort(c.begin(), c.end());
  vector<int> mx(n + 1);
  for(int i = n - 1; i >= 0; i--){
    mx[i] = max(mx[i + 1], c[i].second);
  }
  long long ng = 2e9, ok = -1;
  while(abs(ok - ng) > 1){
    long long mid = (ok + ng) / 2;
    bool check = false;
    for(int i = 0; i < n; i++){
      int j = lower_bound(a.begin(), a.end(), mid - c[i].first) - a.begin();
      j = max(j, i + 1);
      if(j >= n){
        continue;
      }
      long long sumB = c[i].second + mx[j];
      if(sumB >= mid){
        check = true;
        break;
      }
    }
    if(check){
      ok = mid;
    }else{
      ng = mid;
    }
  }
  cout << ok << endl;
}