Submission #677737

#	Time	Username	Problem	Language	Result	Execution time	Memory
677737		puppy	Seesaw (JOI22_seesaw)	C++17	34 / 100	2079 ms	33224 KiB

seesaw

#include <bits/stdc++.h>
#define double long double
#define int long long
using namespace std;
int x[200005];
int s[200005];
int n;
pair<int, int> getavg(int a, int b)
{
    return make_pair(s[b] - s[a-1], b - a + 1);
}
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) s[i] = s[i-1] + x[i];
    vector<pair<int, int>> avg;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            //[i, j] 평균
            avg.push_back(make_pair(s[j] - s[i-1], j - i + 1));
        }
    }
    sort(avg.begin(), avg.end());
    double ans = 1e9;
    for (auto &i:avg) {
        pair<int, int> _min = i; //_min:하계
        double _max = (double)_min.first / _min.second;
        pair<int, int> now = getavg(1, n);
        if (now.first * _min.second < now.second * _min.first) {
            continue;
        }
        _max = (double) now.first / now.second;
        int l = 1, r = n;
        while (l < r) {
            pair<int, int> moved = getavg(l, r - 1);
            if (moved.first * _min.second >= moved.second * _min.first) {
                r--;
                _max = max(_max, (double)moved.first / moved.second);
            }
            else {
                moved = getavg(++l, r);
                _max = max(_max, (double)moved.first / moved.second);
            }
        }
        ans = min(ans, _max - (double)_min.first / _min.second);
    }
    cout.precision(10);
    cout << fixed;
    cout << ans << '\n';
}

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