| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 801814 |
2023-08-02T07:51:59 Z |
ymm |
Seesaw (JOI22_seesaw) |
C++17 |
|
2000 ms |
340 KB |
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
const int N = 200'010;
double pos[N];
double sum;
int n;
pair<double,double> solve(double l)
{
double sum = ::sum;
assert(l <= sum/n);
int p0 = 0, p1 = n-1;
double mn = sum/n, mx = sum/n;
for (int cnt = n; p0 < p1; --cnt) {
if (l <= (sum-pos[p1])/(cnt-1)) {
sum -= pos[p1];
mn = min(mn, sum/(cnt-1));
--p1;
} else {
sum -= pos[p0];
mx = max(mx, sum/(cnt-1));
++p0;
}
}
return {mn, mx};
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop (i,0,n) {
ll x;
cin >> x;
pos[i] = x;
sum += pos[i];
}
double m = sum/n;
double ans = m - pos[0];
double mn = pos[0];
const double eps = 1e-4;
while (m-mn > eps) {
auto [x, y] = solve(mn);
ans = min(ans, y-x);
mn = x+eps;
}
cout << fixed << setprecision(9);
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Execution timed out |
2079 ms |
340 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
2 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Execution timed out |
2079 ms |
340 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
