Submission #700738

#TimeUsernameProblemLanguageResultExecution timeMemory
700738m_fenaisSeesaw (JOI22_seesaw)C++17
0 / 100
11 ms400 KiB
#include <bits/stdc++.h> #define endl '\n' #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define int ll #define all(vec) vec.begin(), vec.end() typedef long long ll; using namespace std; const int N = 200 + 10, mod = 1e9 + 7; int n; double pref[N], mx[N][N], mi[N][N]; void solve(int i, int j, double prev_mi, double prev_mx) { if(i > j) return; double a = double(double(pref[j] - pref[i-1])/double(j-i+1)); if(mi[i][j] == -1) { mi[i][j] = min(prev_mi, a); mx[i][j] = max(prev_mx, a); } else if(abs(double(max(double(prev_mx), double(a))) - double(min(double(prev_mi), double(a)))) < double(mx[i][j] - mi[i][j])) { mi[i][j] = min(prev_mi, a); mx[i][j] = max(prev_mx, a); } solve(i, j - 1, mi[i][j], mx[i][j]); solve(i + 1, j, mi[i][j], mx[i][j]); return; } signed main() { FAST; cin >> n; for(int i = 1; i <= n; i++) cin >> pref[i]; for(int i = 2; i <= n; i++) pref[i] += pref[i-1]; for(int i = 1; i <= n; i++) { for(int j = i; j <= n; j++) { mi[i][j] = -1; mx[i][j] = -1; } } solve(1, n, double(pref[n]/n), double(pref[n]/n)); double ans = INT_MAX; for(int i = 1; i <= n; i++) { ans = min(double(abs(mx[i][i]-mi[i][i])), ans); } cout << fixed << setprecision(9) << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...