Submission #1070880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070880		DeathIsAwe	Sure Bet (CEOI17_sure)	C++17	100 / 100	133 ms	6740 KiB

sure

#include<bits/stdc++.h>
using namespace std;


int main() {
    int n; cin >> n;
    vector<double> fb(n), sb(n), ans(2*n + 1), fp(n + 1), sp(n + 1);
    for (int i=0;i<n;i++) {
        cin >> fb[i] >> sb[i];
    }
    sort(fb.begin(), fb.end(), greater<double>());
    sort(sb.begin(), sb.end(), greater<double>());
    double dum = 0, dummer = 0;
    fp[0] = 0; sp[0] = 0;
    for (int i=0;i<n;i++) {
        dum += fb[i]; fp[i + 1] = dum;
        dummer += sb[i]; sp[i + 1] = dummer;
    }


    ans[0] = 0;
    int top, bottom, middle;
    double negdif, posdif;
    for (int i=1;i<2*n + 1;i++) {
        top = min(i, n); bottom = max(0, i - n);
        if (fp[top] - sp[bottom] <= 0) {
            ans[i] = min(fp[top] - i, sp[bottom] - i);
            continue;
        }
        if (sp[top] - fp[bottom] <= 0) {
            ans[i] = min(sp[top] - i, fp[bottom] - i);
            continue;
        }
        negdif = -10000000000000; posdif = 10000000000000;
        while (top > bottom + 1) {
            middle = (top + bottom) / 2;
            if (fp[middle] - sp[i - middle] < 0) {
                if (fp[middle] - sp[i - middle] > negdif) {
                    negdif = fp[middle] - sp[i - middle];
                }
                bottom = middle;
            } else {
                if (fp[middle] - sp[i - middle] < posdif) {
                    posdif = fp[middle] - sp[i - middle];
                }
                top = middle;
            }
        }
        ans[i] = max(min(fp[top] - i, sp[i - top] - i), min(fp[bottom] - i, sp[i - bottom] - i));
    }

    cout << fixed << setprecision(4);
    cout << *max_element(ans.begin(), ans.end());
}

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