제출 #855495

#제출 시각아이디문제언어결과실행 시간메모리
855495MisterReaperSeesaw (JOI22_seesaw)C++17
0 / 100
0 ms348 KiB
//author: Ahmet Alp Orakci #include <bits/stdc++.h> using namespace std; using i64 = long long; #define int i64 #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 <int> pref = vec; for(int i = 1; i <= n; i++) pref[i] += pref[i -1]; array <double, 2> dp[n +1][n +1]; for(int i = 1; i <= n; i++) dp[i][i] = {double(vec[i]), double(vec[i])}; for(int i = 1; i <= n; i++) { for(int j = 1; j + i <= n; j++) { array <double, 2> l = dp[j][j + i -1], r = dp[j +1][j + i]; double nw = (1.f * pref[j + i] - pref[j -1]) / (i +1); //cerr << j << " " << j + i << " :: " << nw << "\n"; l[0] = min(l[0], nw); l[1] = max(l[1], nw); r[0] = min(r[0], nw); r[1] = max(r[1], nw); if(l[1] - l[0] < r[1] - r[0]) { dp[j][j + i] = l; } else { dp[j][j + i] = r; } } } /* for(int i = 1; i <= n; i++) { for(int j = i; j <= n; j++) { cerr << "{ " << dp[i][j][0] << ", " << dp[i][j][1] << " }" << " \n"[j == n]; } } */ cerr << setprecision(9) << dp[1][n][0] << " " << dp[1][n][1] << "\n"; cout << setprecision(9) << dp[1][n][1] - dp[1][n][0]; 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...