Submission #425653

#TimeUsernameProblemLanguageResultExecution timeMemory
425653oleh1421Sure Bet (CEOI17_sure)C++17
100 / 100
123 ms5264 KiB
#include<bits/stdc++.h> typedef long long ll; using namespace std; const int N=100010; const ll mod=1000000007; const ll inf=1e15; double a[N],b[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<double>v; for (int i=1;i<=n;i++) { cin>>a[i]>>b[i]; v.push_back(a[i]); v.push_back(b[i]); } sort(a+1,a+n+1); sort(b+1,b+n+1); reverse(a+1,a+n+1); reverse(b+1,b+n+1); for (int i=2;i<=n;i++) a[i]+=a[i-1]; for (int i=2;i<=n;i++) b[i]+=b[i-1]; double res=0.0; for (int len=1;len<=2*n;len++){ int l=max(0,len-n); int r=min(n,len); int pos=l; for (int i=20;i>=0;i--){ if (pos+(1<<i)<=r && a[pos+(1<<i)]<=b[len-pos-(1<<i)]) pos+=(1<<i); } for (int i=pos;i<=min(r,pos+1);i++){ int j=len-i; res=max(res,min(a[i]-len,b[j]-len)); } } cout<<setprecision(4)<<fixed<<res<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...