Submission #1347493

#TimeUsernameProblemLanguageResultExecution timeMemory
1347493ChottuFSure Bet (CEOI17_sure)C++20
100 / 100
76 ms6620 KiB
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    long double a[n], b[n];
    for (int i = 0; i<n; i++){
        cin >> a[i] >> b[i];
    }
    sort(a,a+n); reverse(a,a+n);
    sort(b,b+n); reverse(b,b+n);
    
    long double pfa[n+1], pfb[n+1];
    pfa[0] = pfb[0] = 0;
    for (int i = 1; i<=n; i++){
        pfa[i] = pfa[i-1] + a[i-1];
        pfb[i] = pfb[i-1] + b[i-1];
    }
    int yk = 1;
    long double bst = 0;
    for (int x = 1; x<=n; x++){
        int lo = 0;
        int hi = n;
        int nxt = lo;
        while (lo <= hi){
            int mid = (lo+hi)/2;
            long double ee = pfa[x]-x-mid;
            long double rr = pfb[mid]-mid-x;
            if (ee >= rr){
                nxt = max(nxt, mid);
                lo = mid+1;
            }
            else{
                hi = mid-1;
            }
        }
        
        long double aa = pfb[nxt]-x-nxt;
        bst = max(bst, aa);
        if (nxt+1 <= n){
            long double bb = pfa[x]-nxt-1-x;
            bst = max(bst, bb);
        }
    }
    cout << fixed << setprecision(4) << bst;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...