Submission #1358002

#TimeUsernameProblemLanguageResultExecution timeMemory
1358002kutomei3Sure Bet (CEOI17_sure)C++20
100 / 100
41 ms5140 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<double> pa(200001, 0);
vector<double> pb(200001, 0);
double cost(int i, int j) {
    return min(pa[i] - j, pb[j] - j);
}

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

    int n;
    cin >> n;

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

    sort(b.rbegin(), b.rend());
    sort(a.rbegin(), a.rend());

    //cout << '\n';

    pa[0] = a[0];
    pb[0] = b[0]; 
    for (int i = 1; i < n; i++) {
        pa[i] = pa[i - 1] + a[i];
        pb[i] = pb[i - 1] + b[i];
    }

    // cout << '\n';
    // for (int i = 0; i < n; i++) cout << pa[i] << ' ';
    // cout << '\n';
    // for (int i = 0; i < n; i++) cout << pb[i] << ' ';
    //cout << '\n';

    double ans = 0;
    for (int i = 0; i < n; i++) {
        double c = i + 2;
            //cout << ct1 << ' ' << ct2 << '\n';
            //ans = max(ans, min(pa[i] - j, pb[j] - j) - c);
        int l = 0;
        int r = n - 2;
        while (l < r) {
            int mid = (r + l) >> 1;
            if (cost(i, mid) > cost(i, mid + 1)) r = mid;
            else l = mid + 1;
        }
        //cout << l << '\n';
        //for (int j = 0; j < n; j++) cout << cost(i, j) - c << '\n';
        ans = max(ans, max(cost(i, l) - c, cost(i, l + 1) - c));
        //cout << '\n';
    }

    printf("%.4lf", ans);

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...