# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
800051 | amogususus | Sure Bet (CEOI17_sure) | C++17 | 82 ms | 8280 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define prec fixed<<setprecision
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define endl '\n'
#define open(name) if(fopen(name".inp", "r")){freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define fout(name) freopen(name".out", "w", stdout);
using namespace std;
const int maxN=2e5+69;
const int mod=1e9+7;
ll n;
ld a[maxN],b[maxN],pa[maxN],pb[maxN],r=0;
void Enter(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
sort(a+1,a+n+1,greater<ld>());
sort(b+1,b+n+1,greater<ld>());
for(int i=1;i<=n;i++)pa[i]=pa[i-1]+a[i],pb[i]=pb[i-1]+b[i];
for(int i=1;i<=n;i++){
r=max(r,min(pa[i]-2*i ,pb[i] -2*i ));
r=max(r,min(pb[i]-2*i+1,pa[i-1]-2*i+1));
r=max(r,min(pa[i]-2*i+1,pb[i-1]-2*i+1));
}
ll j=0;
for(int i=0;i<=n;i++){
while(j<n&&pb[j+1]<=pa[i])j++;
if(j)r=max(r,min(pa[i]-i-j+1,pb[j-1]-i-j+1));
r=max(r,min(pa[i]-i-j,pb[j]-i-j));
if(j<n)r=max(r,min(pa[i]-i-j-1,pb[j+1]-i-j-1));
}
j=0;
for(int i=0;i<=n;i++){
while(j<n&&pa[j+1]<=pb[i])j++;
if(j)r=max(r,min(pb[i]-i-j+1,pa[j-1]-i-j+1));
r=max(r,min(pb[i]-i-j,pa[j]-i-j));
if(j<n)r=max(r,min(pb[i]-i-j-1,pa[j+1]-i-j-1));
}
cout<<prec(4)<<r;
}
//amogus
signed main(){
open("SUREBET");
cin.tie(nullptr);ios_base::sync_with_stdio(NULL);
//int t=1;cin>>t;while(t--)
Enter();
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |