#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MAX = 200007;
ll S[MAX], on[MAX];
vector<pair<double, int>> P;
double Center(int L, int R) {
return (S[R] - S[L - 1]) / (double)(R - L + 1);
}
void DFS(int L, int R, double init) {
P.emplace_back(Center(L, R), R - L + 1);
if (L == R) return;
double CL = Center(L, R - 1), CR = Center(L + 1, R);
if (init <= CR) DFS(L, R - 1, init);
if (CL <= init) DFS(L + 1, R, init);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> S[i];
S[i] += S[i - 1];
}
int g = N / 2;
double init = S[N] / (double)N;
DFS(1, N, init);
sort(P.begin(), P.end());
double ans = 1e18;
int cnt = 0, R = 0;
on[P[0].second] = 1;
for (int L = 0; L < P.size(); ++L) {
while (R + 1 < P.size() && cnt != N - 1) {
int t = P[++R].second;
if (t != 1 && on[t - 1] && !on[t]) cnt++;
if (t != N && on[t + 1] && !on[t]) cnt++;
on[t]++;
}
if (cnt == N - 1) ans = min(ans, P[R].first - P[L].first);
int t = P[L].second;
on[t]--;
if (t != 1 && on[t - 1] && !on[t]) cnt--;
if (t != N && on[t + 1] && !on[t]) cnt--;
}
cout.precision(12);
cout << fixed << ans;
return 0;
}
Compilation message
seesaw.cpp: In function 'int main()':
seesaw.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int L = 0; L < P.size(); ++L) {
| ~~^~~~~~~~~~
seesaw.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while (R + 1 < P.size() && cnt != N - 1) {
| ~~~~~~^~~~~~~~~~
seesaw.cpp:30:6: warning: unused variable 'g' [-Wunused-variable]
30 | int g = N / 2;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
984 KB |
Output is correct |
3 |
Correct |
2 ms |
984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
984 KB |
Output is correct |
3 |
Correct |
2 ms |
984 KB |
Output is correct |
4 |
Runtime error |
855 ms |
1048576 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
984 KB |
Output is correct |
3 |
Correct |
2 ms |
984 KB |
Output is correct |
4 |
Runtime error |
855 ms |
1048576 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
984 KB |
Output is correct |
3 |
Correct |
2 ms |
984 KB |
Output is correct |
4 |
Runtime error |
855 ms |
1048576 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |