Submission #107957

#	Time	Username	Problem	Language	Result	Execution time	Memory
107957		kingfran1907	Sure Bet (CEOI17_sure)	C++14	100 / 100	147 ms	5240 KiB

sure

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
const int maxn = 1e5+10;
const double inf = 10000000000000;

int n;
long double a[maxn], b[maxn];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();

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

    sort(a, a+n); reverse(a, a+n);
    sort(b, b+n); reverse(b, b+n);

    if (n <= 10) {
        long double sol = 0;
        const int lim = 1 << n;
        for (int i = 0; i < lim; i++) {
            for (int j = 0; j < lim; j++) {
                int kol = __builtin_popcount(i) + __builtin_popcount(j);
                long double a = 0;
                long double b = 0;

                for (int x = 0; x < n; x++)
                    if (i & (1 << x)) a += ::a[x];

                for (int x = 0; x < n; x++)
                    if (j & (1 << x)) b += ::b[x];
                sol = max(sol, min(a, b) - kol);
            }
        }
        cout << fixed << setprecision(4) << sol << endl;
        return 0;
    }

    long double sol = 0;
    long double x = 0, y = 0;
    int ptrx = 0, ptry = 0;
    //a[n] = -inf, b[n] = -inf;
    while (ptrx < n || ptry < n) {
        //cout << "debug: " << x << " " << y << endl;
        //system("pause");
        if (ptrx < n && (min(x + a[ptrx] - 1, y - 1) > min(x - 1, y + b[ptry] - 1) || (min(x + a[ptrx] - 1, y - 1) == min(x - 1, y + b[ptry] - 1) && max(x + a[ptrx] - 1, y - 1) > max(x - 1, y + b[ptrx] - 1)))) {
            x += a[ptrx++] - 1.0;
            y -= 1.0;
        } else {
            y += b[ptry++] - 1.0;
            x -= 1.0;
        }
        if (ptrx + ptry == 1) sol = min(x, y);
        else sol = max(sol, min(x, y));
    }
    cout << fixed << setprecision(4) << sol << endl;
    return 0;
}

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