Submission #108665

#	Time	Username	Problem	Language	Result	Execution time	Memory
108665		someone_aa	Sure Bet (CEOI17_sure)	C++17	100 / 100	245 ms	8652 KiB

sure

#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;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40