oj.uz

Submission #677737

# Submission time Handle Problem Language Result Execution time Memory
677737 2023-01-04T09:11:18 Z puppy Seesaw (JOI22_seesaw) C++17
34 / 100
 2000 ms 33224 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Execution timed out 2079 ms 33224 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Execution timed out 2079 ms 33224 KB Time limit exceeded
9 Halted 0 ms 0 KB -