Submission #677711

#	Time	Username	Problem	Language	Result	Execution time	Memory
677711		benedict0724	Seesaw (JOI22_seesaw)	C++17	1 / 100	1 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 now)
{
    double l, r;
    l = min(A[i], now);
    r = max(A[i], now);
    int s = 1, e = N;
    for(int i=1;i<N;i++)
    {
        double S = (now * (N - i + 1) - A[s]) / (N - i);
        double E = (now * (N - i + 1) - A[e]) / (N - i);
        
        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;
    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, now));
    cout.precision(15);
    cout << ans;
}

Compilation message (stderr)

seesaw.cpp: In function 'int main()':
seesaw.cpp:50:31: warning: 'now' may be used uninitialized in this function [-Wmaybe-uninitialized]
   50 |     for(int i=1;i<=N;i++) now += A[i];
      |                           ~~~~^~~~~~~

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