oj.uz

Submission #957459

# Submission time Handle Problem Language Result Execution time Memory
957459 2024-04-03T18:35:30 Z LucaIlie Seesaw (JOI22_seesaw) C++17
100 / 100
 75 ms 10564 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2488 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2488 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2492 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2488 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2492 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2488 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2492 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 74 ms 10564 KB Output is correct
13 Correct 73 ms 9400 KB Output is correct
14 Correct 74 ms 10204 KB Output is correct
15 Correct 71 ms 9160 KB Output is correct
16 Correct 75 ms 9276 KB Output is correct