Untitled
unknown
c_cpp
a year ago
1.3 kB
2
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