oj.uz

Submission #855624

# Submission time Handle Problem Language Result Execution time Memory
855624 2023-10-01T14:06:30 Z MisterReaper Seesaw (JOI22_seesaw) C++17
67 / 100
 550 ms 1048580 KB 
//Bismillahirrahmanirrahim...
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
 
#define ONLINE_JUDGE
void solve() {
    int n;
    cin >> n;
 
    vector <int> vec(n +1);
    for(int i = 1; i <= n; i++)
        cin >> vec[i];
 
    vector <double> can;
    for(int i = 1; i <= n; i++) {
        i64 sum = 0;
        for(int j = i; j <= n; j++) {
            sum += vec[j];
            can.emplace_back(double(1) * sum / (j - i +1));
        }
    }
 
    i64 top = accumulate(vec.begin(), vec.end(), 0LL);
    double ans = vec[n] - vec[1];
    for(double &mx : can) {
        i64 sum = top; 
 
        double mn = double(1) * sum / n;
        if(mn > mx) {
            continue;
        }
 
        int l = 1, r = n;
        while(l < r) {
            //cerr << l << " " << r << "\n";
            if(sum - vec[l] <= mx * (r - l)) {
                sum -= vec[l];
                l++;
            } else {
                sum -= vec[r];
                r--;
            }
 
            mn = min(mn, double(1) * sum / (r - l +1));

            if(mx - mn >= ans) {
                break;
            }
        }
 
        //cerr << "# " << mx << " " << mn << "\n";
        ans = min(ans, mx - mn);
        //cerr << "\n";
    }
 
    cout << setprecision(15) << ans;
    
    return;
}
 
signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
 
    return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
33.0 / 33.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 27 ms 17868 KB Output is correct
9 Correct 27 ms 18948 KB Output is correct
10 Correct 24 ms 19024 KB Output is correct
11 Correct 19 ms 17612 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 27 ms 17868 KB Output is correct
9 Correct 27 ms 18948 KB Output is correct
10 Correct 24 ms 19024 KB Output is correct
11 Correct 19 ms 17612 KB Output is correct
12 Runtime error 550 ms 1048580 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -