Submission #957459

#TimeUsernameProblemLanguageResultExecution timeMemory
957459LucaIlieSeesaw (JOI22_seesaw)C++17
100 / 100
75 ms10564 KiB
#include <bits/stdc++.h>

using namespace std;

struct cell {
    int l, r;
    double b;
};

const int MAX_N = 2e5;
int a[MAX_N + 1];
long long s[MAX_N + 1];
vector<cell> path;

double bary( int l, int r ) {
    return (double)(s[r] - s[l - 1]) / (r - l + 1);
}

int main() {
    int n;

    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

    int l = 1, r = n;
    while ( l != r ) {
        if ( bary( l, r - 1 ) >= bary( 1, n ) )
            r--;
        else
            l++;
        path.push_back( { l, r, bary( l, r ) } );
    }

    sort( path.begin(), path.end(), []( cell a, cell b ) {
        return a.b > b.b;
    } );

    double minDif = 1e9;
    double minB = bary( 1, n );
    for ( cell c: path ) {
        minDif = min( minDif, c.b - minB );
        minB = min( minB, bary( c.l - 1, c.r - 1 ) );
    }
    minDif = min( minDif, bary( 1, n ) - minB );

    cout << setprecision( 7 ) << fixed << minDif;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...