This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N;
cin >> N;
vector<ll> A(N);
for (int i=0; i<N; i++) cin >> A[i];
double bary[N][N];
set<double> baries;
memset(bary, 0, sizeof bary);
for (int i=0; i<N; i++) {
ll sum = 0;
for (int j=i; j<N; j++) {
sum += A[j];
bary[i][j] = (double)sum / (double)(j - i + 1);
baries.insert(bary[i][j]);
}
}
double ans = 1e9;
double tol = 1e-9;
double dp[N][N];
for (double upper_bound : baries) {
if (upper_bound < bary[0][N-1]-tol) continue;
memset(dp, 0, sizeof dp);
for (int len=0; len<N; len++) {
for (int i=0; i<N-len; i++) {
if (len > 0) {
if (bary[i+1][i+len] < upper_bound+tol) {
dp[i][i+len] = min(bary[i][i+len], max(
dp[i+1][i+len],
dp[i][i+len-1]
));
} else {
dp[i][i+len] = min(bary[i][i+len], dp[i][i+len-1]);
}
} else {
dp[i][i+len] = bary[i][i+len];
}
}
}
// cout << upper_bound << ":\n";
// for (int i=0; i<N; i++) {
// for (int j=0; j<N; j++) {
// cout << dp[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
ans = min(ans, upper_bound - dp[0][N-1]);
}
cout << setprecision(100) << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |