Submission #1153049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153049		_8_8_	Seesaw (JOI22_seesaw)	C++20	0 / 100	0 ms	328 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];
ll p[N];

double get(int l, int r) {
    return (1.0 * (p[r] - p[l - 1])) / (1.0 * (r - l + 1));
}
double solve_mx(int l, int r, double mn, double mx) {
    while(r < n || l > 1) {
        if(r + 1 <= n && get(l, r + 1) <= mx) {
            r++;
        } else {
            if(l == 1) {
                return inf;
            }
            l--;
        }
        mn = min(mn, get(l, r));
    }
    return mx - mn;
}
double solve_mx1(int l, int r, double mn, double mx) {
    double mxx = a[l];
    while(r < n || l > 1) {
        if(r + 1 <= n && get(l, r + 1) <= mx) {
            r++;
        } else {
            if(l == 1) {
                return inf;
            }
            l--;
        }
        mn = min(mn, get(l, r));
        mxx = max(mxx, get(l, r));
    }
    return mxx - mn;
}
double solve_mn(int l, int r, double mn, double mx) {
    while(r < n || l > 1) {
        if(l - 1 >= 1 && get(l - 1, r) >= mn) {
            l--;
        } else {
            if(r == n) return inf;
            r++;
        }
        mx = max(mx, get(l, r));
    }
    return mx - mn;
}
double solve_mn1(int l, int r, double mn, double mx) {
    double mnn = a[l];
    while(r < n || l > 1) {
        if(l - 1 >= 1 && get(l - 1, r) >= mn) {
            l--;
        } else {
            if(r == n) return inf;
            r++;
        }
        mx = max(mx, get(l, r));
        mnn = min(mnn, get(l, r));
    }
    return mx - mnn;
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }
    double res = inf;
    for(int i = 1; i <= n; i++) {
        res = min(res, solve_mn(i, i, a[i], a[i]));
        res = min(res, solve_mx(i, i, a[i], a[i]));
        if(i + 1 <= n) {
            res = min(res, solve_mn(i, i + 1, a[i], get(i, i + 1)));
            res = min(res, solve_mx(i, i + 1, a[i], get(i, i + 1)));
            res = min(res, solve_mx1(i, i, a[i], a[i + 1]));
        }
        if(i - 1 >= 1) {
            res = min(res, solve_mn(i - 1, i, get(i - 1, i), a[i]));
            res = min(res, solve_mx(i - 1, i, get(i - 1, i), a[i]));
            res = min(res, solve_mn1(i, i, a[i - 1], a[i]));
        }
    }
    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: 0 / 1
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33