제출 #1265158

#제출 시각아이디문제언어결과실행 시간메모리
1265158JerSure Bet (CEOI17_sure)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5;

int n;
double a[MAXN], b[MAXN];

double solve(int i){
    double pa = 0, pb = 0;
    int used = 0, inda = 0, indb = 0;

    while (pa < i and used < i and inda < n)
        pa += a[inda++], used++;
    while (pb < i and used < i and indb < n)
        pb += b[indb++], used++;

    while (used < i and (inda < n or indb < n)){
        if (inda < n and pa < pb)
            pa += a[inda++];
        else
            pb += b[indb++];
        used++;
    }

    return min(pa - double(i), pb - double(i));
}

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

    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 res = 0;
    int low = 0, high = 2 * n;
    
    while (low < high){
        int mid = (low + high) / 2;
        double curr = solve(mid);

        res = max(res, curr);

        if (curr > solve(mid + 1))
            high = mid;
        else
            low = mid + 1;
    }
    
    printf("%.4f\n", res);
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...