Submission #609738

#TimeUsernameProblemLanguageResultExecution timeMemory
609738MasterTasterSure Bet (CEOI17_sure)C++14
100 / 100
78 ms3608 KiB
#include <bits/stdc++.h>

#define pb push_back
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define MAXN 100010

using namespace std;

int n;
double eps=0.000001;
double ress=0, a[MAXN], b[MAXN];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n;
    for (int i=0; i<n; i++) cin>>a[i]>>b[i];

    sort(a, a+n, greater<double>());
    sort(b, b+n, greater<double>());

    double aa=0, bb=0;
    int i=0, j=0;
    while (i<n || j<n)
    {
        if ((bb+eps)<=aa)
        {
            if (j==n) break;
            bb+=b[j++];
        }
        else
        {
            if (i==n) break;
            aa+=a[i++];
        }
        ress=max(ress, min(aa-i-j, bb-i-j));
    }
    cout<<fixed<<showpoint<<setprecision(4)<<ress<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...