fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int T;
  10.     cin >> T;
  11.     while (T--) {
  12.         int N;
  13.         cin >> N;
  14.         vector<pair<ll,ll>> mons(N);
  15.         for (int i = 0; i < N; i++) {
  16.             cin >> mons[i].first >> mons[i].second; // {A, B}
  17.         }
  18.  
  19.         // Sort by endurance B ascending
  20.         sort(mons.begin(), mons.end(),
  21.              [](auto &m1, auto &m2){
  22.                  return m1.second < m2.second;
  23.              });
  24.  
  25.         priority_queue<ll> pq; // max-heap of powers A
  26.         ll sumA = 0;
  27.         int best = 0;
  28.  
  29.         for (auto &m : mons) {
  30.             ll A = m.first;
  31.             ll B = m.second;
  32.             // include this monster
  33.             sumA += A;
  34.             pq.push(A);
  35.             // if average power > B, drop the monster with largest A
  36.             while (!pq.empty() && sumA > (ll)pq.size() * B) {
  37.                 sumA -= pq.top();
  38.                 pq.pop();
  39.             }
  40.             best = max(best, (int)pq.size());
  41.         }
  42.  
  43.         cout << best << "\n";
  44.     }
  45.  
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1
5
10 2
8 10
5 7
7 4
8 7
stdout
copy 
3
https://ideone.com/6pxQDk
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!