Submission #677784

#	Time	Username	Problem	Language	Result	Execution time	Memory
677784		benedict0724	Seesaw (JOI22_seesaw)	C++17	0 / 100	0 ms	212 KiB

seesaw

#include <iostream>
#include <stack>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>

using namespace std;
typedef long long ll;

double A[200002];
int N;

double solve(int i)
{
    double l, r;
    l = A[i];
    r = A[i];
    int s = i, e = i;
    double now = A[i];
    for(int i=1;i<N;i++)
    {
        double S = (now * i + A[s-1]) / (i + 1);
        double E = (now * i + A[e+1]) / (i + 1);
        
        if(s == 1)
        {
            now = E;
            e++;
        }
        else if(e == N)
        {
            now = S;
            s--;
        }
        else if(max(r, S) - min(l, S) <= max(r, E) - min(l, E))
        {
            now = S;
            s--;
        }
        else
        {
            now = E;
            e++;
        }
        r = max(r, now);
        l = min(l, now);
    }
    return r - l;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for(int i=1;i<=N;i++) cin >> A[i];
    double now = 0;
    for(int i=1;i<=N;i++) now += A[i];
    now /= N;
    double ans = A[N] - A[1];
    for(int i=1;i<=N;i++) ans = min(ans, solve(i));
    cout.precision(15);
    cout << ans;
}

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