#include <bits/stdc++.h>
//#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef const int cint;
typedef vector<int> vint;
typedef double ld;
#define fr(i,a,b) for(int i=(a); i<=(b); ++i)
#define rr(i,a,b) for(int i=(a); i>=(b); --i)
#define fv(i,x) for(auto& i:x)
#define fp(p,q,x) for(auto& [p, q]:x)
#define pb push_back
#define in insert
#define f first
#define s second
#define mn 500009
#define mn2 1048576
int n;
map<pair<ld, ld>, bool> mp;
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
vector<pair<ld, ld>> v(n);
fp(a, b, v) cin>>a>>b;
vector<pair<ld, ld>> w=v;
sort(v.begin(), v.end(), [](pair<ld, ld> a, pair<ld, ld> b){ return a.f>b.f; } );
sort(w.begin(), w.end(), [](pair<ld, ld> a, pair<ld, ld> b){ return a.s>b.s; } );
//fv(it, w) cout<<it.s<<" ";
//cout<<"\n";
ld l=0, p=0;
int i=0, j=0;
ld wyn=0;
int il=0;
while(i<n && j<n){
if(l<p){
while(mp[v[i]] && i<n){
++i;
if(i>=n) break;
}
if(i>=n) break;
l+=v[i].f;
++il;
mp[v[i]]=1;
}
else{
while(mp[w[j]] && j<n){
++j;
if(j>=n) break;
}
if(j>=n) break;
p+=w[j].s;
++il;
mp[w[j]]=1;
}
//cout<<l<<" "<<p<<"\n";
wyn=max(wyn, min(p, l)-il);
}
//cout<<"\n";
// fp(a, b, v){
// if(l<=p) l+=a;
// else p+=b;
// cout<<l<<" "<<p<<" "<<a<<" "<<b<<"\n";
// }
cout<<fixed<<setprecision(4)<<wyn;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |