#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<double> fb(n), sb(n), ans(2*n + 1), fp(n + 1), sp(n + 1);
for (int i=0;i<n;i++) {
cin >> fb[i] >> sb[i];
}
sort(fb.begin(), fb.end(), greater<double>());
sort(sb.begin(), sb.end(), greater<double>());
double dum = 0, dummer = 0;
fp[0] = 0; sp[0] = 0;
for (int i=0;i<n;i++) {
dum += fb[i]; fp[i + 1] = dum;
dummer += sb[i]; sp[i + 1] = dummer;
}
ans[0] = 0;
int top, bottom, middle;
double negdif, posdif;
for (int i=1;i<2*n + 1;i++) {
top = min(i, n); bottom = max(0, i - n);
if (fp[top] - sp[bottom] <= 0) {
ans[i] = min(fp[top] - i, sp[bottom] - i);
continue;
}
if (sp[top] - fp[bottom] <= 0) {
ans[i] = min(sp[top] - i, fp[bottom] - i);
continue;
}
negdif = -10000000000000; posdif = 10000000000000;
while (top > bottom + 1) {
middle = (top + bottom) / 2;
if (fp[middle] - sp[i - middle] < 0) {
if (fp[middle] - sp[i - middle] > negdif) {
negdif = fp[middle] - sp[i - middle];
}
bottom = middle;
} else {
if (fp[middle] - sp[i - middle] < posdif) {
posdif = fp[middle] - sp[i - middle];
}
top = middle;
}
}
ans[i] = max(min(fp[top] - i, sp[i - top] - i), min(fp[bottom] - i, sp[i - bottom] - i));
}
cout << fixed << setprecision(5);
cout << *max_element(ans.begin(), ans.end());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
