Submission #1225863

#TimeUsernameProblemLanguageResultExecution timeMemory
1225863mariamtsagareliSure Bet (CEOI17_sure)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<double>a(n),b(n);
    for(int i=0;i<n;i++)cin>>a[i]>>b[i];
    sort(a.begin(),a.end(),greater<double>());
    sort(b.begin(),b.end(),greater<double>());
    vector<double>A(n+1),B(n+1);
    for(int i=1;i<=n;i++){
        A[i]=A[i-1]+a[i-1];
        B[i]=B[i-1]+b[i-1];
    }
    double r=0;
    for(int i=0;i<=n;i++){
        int l=0,h=n;
        while(l<h){
            int m=(l+h+1)/2;
            if(B[m]>=A[i]) l=m;
            else h=m-1;
        }
        int j=l;
        auto u=[&](int k){
            if(k<0||k>n) return;
            double p=min(A[i],B[k])-(i+k);
            if(p>r) r=p;
        };
        u(j);
        u(j+1);
    }
    if(r<0) r=0;
    cout<<fixed<<setprecision(4)<<r<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...