Submission #1319791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319791		harryleee	Seesaw (JOI22_seesaw)	C++20	1 / 100	14 ms	460 KiB

seesaw

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5;
const int inf = 1e9;
long double n, a[maxn + 1];

namespace sub1{
    long double recur(int i, int j, long double l, long double r){
        long double cur = 0;
        for (int ind = i; ind <= j; ++ind){
            cur += (long double) a[ind];
        }
        cur /= (long double) (j - i + 1);

        l = min(l, cur);
        r = max(r, cur);

        if (i == j) 
            return r - l;
        return min(recur(i + 1, j, l, r), recur(i, j - 1, l, r));
    }

    long double solve(){
        return recur(1, n, inf + 1, -1);
    }
}

namespace sub3{
    long double pre[maxn + 1];

    long double solve(){
        long double res = inf + 1;
        for (int i = 1; i <= n; ++i){
            pre[i] = pre[i - 1] + a[i];
        }
        for (int i = 1; i <= n; ++i){
            long double l = a[i], r = a[i];
            int u = i, v = i;
            
            while(u != 1 || v != n){
                if (u == 1){
                    v++;
                    r = max(r, (pre[v] - pre[u - 1]) / (long double) (v - u + 1));
                }
                else if (v == n){
                    u--;
                    l = min(l, (pre[v] - pre[u - 1]) / (long double) (v - u + 1));
                }
                else{
                    long double move_left = (pre[v] - pre[u - 2]) / (long double) (v - u + 2);
                    long double move_right = (pre[v + 1] - pre[u - 1]) / (long double) (v - u + 2);
                    if (l - move_left < move_right - r){
                        u--;
                        l = min(l, move_left);
                    }
                    else{
                        v++;
                        r = max(r, move_right);
                    }
                }
            }
            // cout << l << ' ' << r << '\n';
            res = min(res, r - l);
        }

        return res;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    if (n <= 20){
        cout << fixed << setprecision(9) << sub1::solve();
    }
    else if (n <= 2000){
        cout << fixed << setprecision(9) << sub3::solve();
    }
}

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