// I was grinning like I'm winning, I was hitting my marks
// 'Cause I can do it with a broken heart
// 1 2 3 4 ...
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <bitset>
typedef long long ll;
typedef long double ld;
using namespace std;
vector<ll> a, pf;
ld avg(int l, int r) { return (ld)(pf[r + 1] - pf[l]) / (ld)(r - l + 1); }
void chmax(ld& a, ld b) { a = max(a, b); }
void chmin(ld& a, ld b) { a = min(a, b); }
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
a.assign(n, 0), pf.assign(n + 1, 0);
for (int i = 0; i < n; i++) cin >> a[i], pf[i + 1] = pf[i] + a[i];
ld w = avg(0, n - 1);
vector<pair<ld, int>> v;
v.push_back({ avg(0, n - 1), n });
v.push_back({ avg(0, n - 2), n - 1 });
v.push_back({ avg(1, n - 1), n - 1 });
int l = 0;
for (int i = n - 2; i >= 1; i--)
{
if (avg(l + 1, l + i) <= w) l++;
v.push_back({ avg(l, l + i - 1), i });
v.push_back({ avg(l + 1, l + i), i });
}
ld ans = w;
stable_sort(v.begin(), v.end());
vector<int> f(n + 1, 0);
int cnt = 0, r = 0;
for (int l = 0; l < v.size(); l++)
{
while (cnt < n && r < v.size())
{
if (!f[v[r].second]) cnt++;
f[v[r].second]++;
r++;
}
if (cnt == n) ans = min(ans, v[r - 1].first - v[l].first);
f[v[l].second]--;
if (!f[v[l].second]) cnt--;
}
cout << setprecision(9) << fixed;
cout << ans << "\n";
return 0;
}
Compilation message
seesaw.cpp: In function 'int main()':
seesaw.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int l = 0; l < v.size(); l++)
| ~~^~~~~~~~~~
seesaw.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long double, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | while (cnt < n && r < v.size())
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
376 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
376 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
600 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
376 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
724 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
93 ms |
30660 KB |
Output is correct |
13 |
Correct |
100 ms |
30512 KB |
Output is correct |
14 |
Correct |
108 ms |
30652 KB |
Output is correct |
15 |
Correct |
99 ms |
30612 KB |
Output is correct |
16 |
Correct |
91 ms |
30696 KB |
Output is correct |