Submission #576262

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

sure

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

int main(){

    int n;
    std::cin >> n;

    std::vector<double> a, b;

    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());
    sort(b.rbegin(), b.rend());

    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 - 1, best_j = -1;

        while(lo <= hi) {
            int j = (lo + hi) / 2;
            if( a[i] - j - 1 <= b[j] - i - 1 ) {
                hi = j - 1;
                best_j = j;
            } else {
                lo = j + 1;
            }
        }

        if(best_j != -1) {
            ans = std::max(ans, std::min(a[i] - best_j - 1, b[best_j] - i - 1));
        }
    }

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

    return 0;
}

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