Submission #957459

#	Time	Username	Problem	Language	Result	Execution time	Memory
957459		LucaIlie	Seesaw (JOI22_seesaw)	C++17	100 / 100	75 ms	10564 KiB

seesaw

#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;
}

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