Submission #1357984

#TimeUsernameProblemLanguageResultExecution timeMemory
1357984kutomei3Sure Bet (CEOI17_sure)C++20
60 / 100
2095 ms4932 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;
        for (int j = 0; j < n; j++) {
            //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, l) > cost(i, l + 1)) r = mid;
                else l = mid + 1;
            }
            //cout << cost(i, l) - c << '\n';
            ans = max(ans, min(cost(i, l) - c, cost(i + 1, l) - c));
        }
        //cout << '\n';
    }

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

    return 0;
}

/*
max    (min(a[i] - j, b[j] - j) - i))
a[i] < a[i + 1] - 1
l = a[i] - i
k = b[j] - j
0<=i,j<n

min(a[i] - j, b[j] - j)
b[j] < b[j + 1]
j
*/
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...