Submission #856325

#	Time	Username	Problem	Language	Result	Execution time	Memory
856325		Alexandruabcde	Sure Bet (CEOI17_sure)	C++14	100 / 100	70 ms	3692 KiB

sure

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;

int N;

double A[NMAX];
double B[NMAX];

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

    cin >> N;

    for (int i = 1; i <= N; ++ i ) {
        cin >> A[i] >> B[i];
    }

    sort(A+1, A+N+1);
    sort(B+1, B+N+1);

    for (int i = N - 1; i >= 1; -- i )
        B[i] += B[i+1];

    double answer = 0;
    double sumA = 0;

    for (int i = N+1; i >= 1; -- i ) {
        sumA += A[i];
        int paidA = (N - i + 1);

        int st = 1, dr = N;
        int pos = N + 1;

        while (st <= dr) {
            int mij = (st + dr) / 2;

            double curr_case = min(sumA - paidA - (N - mij + 1), B[mij] - paidA - (N - mij + 1));
            double ant_case = min(sumA - paidA - (N - (mij+1) + 1), B[mij+1] - paidA - (N - (mij+1) + 1));

            if (curr_case >= ant_case) {
                pos = mij;
                dr = mij - 1;
            }
            else st = mij + 1;
        }

        double sumB = B[pos];
        int paidB = N - pos + 1;

        answer = max(answer, min(sumA - paidA - paidB, sumB - paidA - paidB));
    }

    cout << setprecision(4) << fixed << answer << '\n';

    return 0;
}

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