Submission #1027314

#TimeUsernameProblemLanguageResultExecution timeMemory
1027314vjudge1Sure Bet (CEOI17_sure)C++17
0 / 100
2037 ms4444 KiB
#include<bits/stdc++.h> #define ll long long int #define pb push_back #define yy cout<<"YES"<<endl; #define nn cout<<"NO"<<endl; #define ld long double #define T ll t;cin>>t;while(t--){solve();} #define funfact for(ll i=1 ; i<=n ; i++){cout<<a[i]<<" ";} using namespace std; const ll N=2e5,mod=1e9+7,inf=1e18; ld a[N],b[N]; ld prea[N],preb[N]; ll n; //----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------// bool cmp (ld x,ld y) { return x>y; } ld f(ll x,ll y) { return min(prea[x]-1.0*y,preb[y]-1.0*x); } ld bin(ll x) { ll l=1,r=n; ld ans=-1; if(n == 1) return f(x, 1); if(n == 2) return max(f(x, 1), f(x, 2)); while (l<=r) { ll md=(l+r)/2; ll fi=md-1,se=md,th=md+1; if (fi==0) { ans=md,l=md+1; continue; } if (th==n+1) { ans=md,r=md-1; continue; } if (f(x,fi)<f(x,se)&&f(x,se)>f(x,th)) { ans=md,l=md+1; } else if (f(x,fi)>f(x,se)&&f(x,se)) { ans=md,r=md-1; } else if (f(x,fi)<f(x,se)&&f(x,se)>f(x,th)) { return f(x,se); } } return f(x,ans); } void solve(){ cin>>n; for (ll i=1;i<=n;i++) { cin>>a[i]>>b[i]; a[i]--; b[i]--; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); ld ans=0.0; for (ll i=1;i<=n;i++){ prea[i]+=prea[i-1]+a[i]; preb[i]+=preb[i-1]+b[i];} for (ll i=n;i>=1;i--) { ans=max(ans,bin(i)); } cout<<fixed<<setprecision(4)<<ans<<endl; } int main(){ solve(); } /* This code is created by anhluong -------Copy code is prohibiited in any form -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...