oj.uz

Submission #576265

# Submission time Handle Problem Language Result Execution time Memory
576265 2022-06-12T20:02:01 Z mmonteiro Sure Bet (CEOI17_sure) C++17
0 / 100
 1 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -