제출 #108665

#제출 시각아이디문제언어결과실행 시간메모리
108665someone_aaSure Bet (CEOI17_sure)C++17
100 / 100
245 ms8652 KiB
#include <bits/stdc++.h>
#define ld long double
using namespace std;
const int N = 100100;
vector<ld> a, b;
ld apref[N], bpref[N];
int n;

ld f(int a, int x) {
    return min(bpref[a]-(a+x), apref[x]-(a+x));
}

int bin_search(int x) {
    // searching in b, x
    int index = 0;
    for(int cekor = n; cekor > 0; cekor/=2) {
        while(index + cekor <= n && f(index+cekor, x)<f(index+cekor+1, x)) index+=cekor;
    }
    return index+1;
}

int main() {
    cin>>n;
    ld x, y;
    for(int i=0;i<n;i++) {
        cin>>x>>y;
        a.push_back(x);
        b.push_back(y);
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    for(int i=1;i<=n;i++) {
        apref[i] = apref[i-1] + a[i-1];
        bpref[i] = bpref[i-1] + b[i-1];
    }

    ld result = 0;
    for(int i=1;i<=n;i++) {
        int x = bin_search(i);
        result = max(result, min(apref[i]-(i+x), bpref[x]-(i+x)));
    }
    cout<<setprecision(4)<<fixed<<result<<"\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...