Submission #1154980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154980		_8_8_	Seesaw (JOI22_seesaw)	C++20	100 / 100	86 ms	13072 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define double long double
#define int ll
const int N = (int)1e6 + 10, MOD = (int)1e9 + 7, inf = (int)2e9;

int n, a[N], p[N];

double s[N];
double get(int l, int r) {
    return (1.0 * (p[r] - p[l - 1])) / (1.0 * (r - l + 1)) ;
}
array<double, 2> c[N];
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    double f = get(1, n);
    for(int i = 1; i < n; i++) {
        int l = 1, r = n - i + 1;
        while(r - l > 1) {
            int mid = (l + r) >> 1;
            if(get(mid, mid + i - 1) > f) {
                r = mid;
            } else {
                l = mid;
            }
        }
        // cout << i << ' ' << l << ' ' << r << '\n';
        c[i] = {get(r, r + i - 1), get(l, l + i - 1)};
    }
    sort(c + 1, c + n);
    for(int i = 1; i < n; i++) swap(c[i][0], c[i][1]);
    s[n] = inf;
    for(int i = n - 1; i >= 1; i--) {
        s[i] = min(s[i + 1], c[i][0]);
    }
    for(int i = 1; i < n; i++) {
        // cout << c[i][0] << ' ' << c[i][1] << '\n';
    }
    double res = inf;
    for(int i = 0; i < n; i++) {
        double val = (i == n - 1 ? f : s[i + 1]);
        res = min(res, max(f, c[i][1]) - val);
        // cout << i << ' ' << max(f, c[i][1]) - val << ' ' << val << '\n';
    }
    cout << fixed << setprecision(10) << res << '\n';
}

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

    int t = 1;
    // cin >> t;

    while(t--) {
        test();
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33