Submission #672606

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

seesaw

#include <bits/stdc++.h>
// #include <atcoder/string>
// #include <atcoder/lazysegtree>

using namespace std;


using ll = long long;
using ull = unsigned long long;
// using mint = atcoder::modint998244353;
int INF = numeric_limits<int>::max() >> 1;
ll INFL = numeric_limits<ll>::max() >> 1;
ll mod = 998244353;


vector<ll> prefixSums;

ll getSum(int l, int r)
{
    return prefixSums[r + 1] - prefixSums[l];
}

double computeLength(double start, vector<ll> &a)
{
    int n = a.size(), l = 0, r = n - 1;
    double maxRight = (double)getSum(l, r) / n;
    for (int i = 0; i < n - 1; i++)
    {
        if ((double)getSum(l, r - 1) / (r - l) >= start)
        {
            r--;
        }
        else
        {
            maxRight = max(maxRight, (double)getSum(l + 1, r) / (r - l));
            l++;
        }
    }
    return maxRight - start;
}

void solve()
{
    ll n;
    cin >> n;
    vector<ll> a(n);
    prefixSums.resize(n + 1);
    prefixSums[0] = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        prefixSums[i + 1] = prefixSums[i] + a[i];
    }

    double l = a[0], r = (double)prefixSums[n] / n, ll, rr;

    while (r - l > 1e-11)
    {
        ll = (2 * l + r) / 3;
        rr = (l + 2 * r) / 3;

        auto len1 = computeLength(ll, a), len2 = computeLength(rr, a);

        if (len1 > len2)
        {
            l = ll;
        }
        else
        {
            r = rr;
        }
    }

    cout << fixed << setprecision(12) << computeLength(l, a) << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    // precompute(200005);
	int t;
	t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++)
	{
		// cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
};

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