Submission #866904

#	Time	Username	Problem	Language	Result	Execution time	Memory
866904		sleepntsheep	Sure Bet (CEOI17_sure)	C++17	60 / 100	2051 ms	6512 KiB

sure

#include <cstdio>
#include <iomanip>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

int n;
ld a[N], b[N];

int ok(ld x)
{
    for (int take = 0; take <= 2*n; ++take)
    {
        int l = max(0,n-take), r = n-1, L=-1, R=-1;
        while (l <= r)
        {
            int y = (l+r)/2;
            if (a[y] - take >= x) l=y+1, L=y;
            else r=y-1;
        }
        if (L==-1) continue;
        R = n-take+(n-L);
        if (b[R] - take >= x) return 1;
    }
    return 0;
}

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i];
    sort(a, a+n), sort(b, b+n);
    for (int i = n; i--;) a[i] += a[i+1], b[i] += b[i+1];

    ld l = 0, r = 1e9, iter=300;
    for (; --iter;)
    {
        ld y = (l+r)/2;
        if (ok(y)) l = y;
        else r = y;
    }
    cout << fixed << setprecision(4) << l;

    return 0;
}

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