Submission #1096787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096787		ooscode	Seesaw (JOI22_seesaw)	C++17	0 / 100	0 ms	348 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define F first
#define S second
#define pb push_back
#define all(x) x.begin() , x.end()
#define debug while(1) cout << "Test\n"

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target ("avx2")

const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 1e15 + 10;

int pref[N];
int a[N];
int n;

long double f(int l , int r) {
    return (long double) (pref[r] - pref[l-1]) / (r - l + 1);
}

void solve() {
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i] , pref[i] = pref[i-1] + a[i];

    int l = 1;
    int r = n;

    long double mn , ans , w = f(l , r); mn = ans = w;

    for(int i = n-1 ; i ; i--) {
        long double x = f(l + 1 , r);
        if(x <= w) {l++ , ans = x; continue;}

        ans = f(l , --r);
        mn = min(mn , ans);
    }    

    long double mx; mx = ans = w;
    l = 1;
    r = n;

    for(int i = n-1 ; i ; i--) {
        long double x = f(l , r - 1);
        if(x >= w) {r-- , ans = x; continue;}

        ans = f(++l , r);
        mx = max(mx , ans);
    }

    cout << fixed << setprecision(20) << min(w - mn , mx - w) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
}

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