oj.uz

Submission #856324

# Submission time Handle Problem Language Result Execution time Memory
856324 2023-10-03T06:17:28 Z Alexandruabcde Sure Bet (CEOI17_sure) C++14
0 / 100
 0 ms 348 KB 
#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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -