Submission #810577

#	Time	Username	Problem	Language	Result	Execution time	Memory
810577		caganyanmaz	Seesaw (JOI22_seesaw)	C++17	34 / 100	2060 ms	37176 KiB

seesaw

#include <bits/stdc++.h>
#define pb push_back

#define int int64_t
using namespace std;

constexpr static int INF = 3e14;
constexpr static double EPSILON = 0.000000000001;

constexpr static int MXSIZE = 5001;
int v[MXSIZE];
vector<double> vv[MXSIZE];
vector<double> all;

int32_t main()
{
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
                cin >> v[i];
        for (int l = 0; l < n; l++)
        {
                int sum = 0;
                for (int r = l+1; r <= n; r++)
                {
                        sum += v[r-1];
                        vv[r-l].pb(static_cast<double>(sum) / (r-l));
                        all.pb(vv[r-l].back());
                }
        }
        for (int i = 0; i <= n; i++)
                sort(vv[i].begin(), vv[i].end());
        double best = INF;
        for (double d : all)
        {
                double left = INF, right = 0;
                for (int i = 1; i <= n; i++)
                {
                        auto it = lower_bound(vv[i].begin(), vv[i].end(), d);
                        if (it == vv[i].end())
                        {
                                left = 0, right = INF;
                                break;
                        }
                        left = min(left, *it);
                        right = max(right, *it);
                }
                best = min(best, right - left);
        }
        cout << fixed;
        cout << setprecision(100);
        cout << best << "\n";
}

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