Submission #576264

#	Time	Username	Problem	Language	Result	Execution time	Memory
576264		mmonteiro	Sure Bet (CEOI17_sure)	C++17	0 / 100	1 ms	252 KiB

sure

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <iomanip>

int main(){

    int n;
    std::cin >> n;

    std::vector<double> a = {0.0}, b = {0.0};

    for(int i = 0; i < n; i++){
        double x, y;
        std::cin >> x >> y;
        a.push_back(x - 1.0);
        b.push_back(y - 1.0);
    }

    sort(a.rbegin(), a.rend() - 1);
    sort(b.rbegin(), b.rend() - 1);

    for(int i = 1; i < n; ++i) {
        a[i] += a[i - 1];
        b[i] += b[i - 1];
    }

    double ans = 0.0;

    for(int i = 0; i <= n; ++i) {
        int lo = 0, hi = n, best_j = 0;
        while(lo <= hi) {
            int j = (lo + hi) / 2;
            if( a[i] - j <= b[j] - i ) {
                hi = j - 1;
                best_j = j;
            } else {
                lo = j + 1;
            }
        }
        ans = std::max(ans, std::min(a[i] - best_j, b[best_j] - i));
    }

    std::cout << std::fixed << std::setprecision(4) << ans << std::endl;

    return 0;
}

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