Submission #962265

#	Time	Username	Problem	Language	Result	Execution time	Memory
962265		LucaIlie	Sure Bet (CEOI17_sure)	C++17	100 / 100	142 ms	5160 KiB

sure

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const long long MAX_P = 1e15;
const double EPS = 1e-5;
double a[MAX_N + 1], b[MAX_N + 1], sa[MAX_N + 1], sb[MAX_N + 1];

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ )
        cin >> a[i] >> b[i];

    sort( a + 1, a + 1 + n );
    reverse( a + 1, a + 1 + n );
    sort( b + 1, b + 1 + n );
    reverse( b + 1, b + 1 + n );
    for ( int i = 1; i <= n; i++ ) {
        sa[i] = sa[i - 1] + a[i];
        sb[i] = sb[i - 1] + b[i];
    }

    double l = 0, r = MAX_P;
    while ( r - l > EPS ) {
        double p = (l + r) / 2;

        bool isPos = false;
        for ( int i = 0; i <= n; i++ ) {
            int j = min( (double)n, max( 0.0, (sa[i] - i - p) ) );
            if ( min( sa[i], sb[j] ) - (i + j)  >= p )
                isPos = true;
        }

        if ( isPos )
            l = p;
        else
            r = p;
    }

    cout << fixed << setprecision( 4 ) << l;

    return 0;
}

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