Submission #855566

#TimeUsernameProblemLanguageResultExecution timeMemory
855566MisterReaperSeesaw (JOI22_seesaw)C++17
34 / 100
2063 ms17100 KiB
//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 = 1E18; 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)); } //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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...