oj.uz

Submission #576262

# Submission time Handle Problem Language Result Execution time Memory
576262 2022-06-12T19:33:59 Z mmonteiro Sure Bet (CEOI17_sure) C++17
0 / 100
 1 ms 296 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 296 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 0 ms 296 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 0 ms 296 KB Output isn't correct
3 Halted 0 ms 0 KB -