Untitled

 avatar
unknown
c_cpp
4 months ago
1.3 kB
1
Indexable
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const int dx[]{-1,+1,+0,+0,-1,-1,+1,+1};
const int dy[]{+0,+0,+1,-1,-1,+1,-1,+1};
const int MOD = 1e9+7;
#define int long long
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>
ordered_set;

#define ld long double

// upsolved
void solve(int testCase){
   int n;
   cin >> n;
   std::vector<array<int,2>> v(n);
   for(int i = 0; i < n; ++i) cin >> v[i][0] >> v[i][1];
   sort(v.begin(), v.end());
   priority_queue<array<int,2>, vector<array<int,2>>, greater<array<int,2>>> q;
   int sum = 0, len = 0, ans = 0;
   for(int i = 0; i < n; ++i){
       q.push({v[i][1], v[i][0]});
       sum += v[i][0];
       ++len;
       while(!q.empty() && q.top()[0] * len < sum){
          sum -= q.top()[1];
          --len;
          q.pop();
       }
       ans = max(ans, len);
   }
   cout << ans << '\n';
}

int32_t main(){
    freopen("monsters.in", "r", stdin);
    fastio();  
    int t = 1;
    cin >> t;     
    for(int i = 1; i <= t; ++i){
        solve(i);
    }
    return 0;
}
Editor is loading...
Leave a Comment