#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
double a[MAXN], b[MAXN];
//double parca[MAXN], parcb[MAXN];
int an, bn;
int bs(double a[], double b[], int an, int l, int r) {
int rez = 0;
while(l <= r) {
int mid = (l+r)/2;
if(a[an]-mid >= b[mid]-an) rez = mid, l = mid+1;
else r = mid-1;
}
return rez;
}
int main() {
ios::sync_with_stdio(false);cin.tie(0);
int n; cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
sort(a+1, a+n+1);
sort(b+1, b+n+1);
reverse(a+1, a+n+1);
reverse(b+1, b+n+1);
for(int i = 1; i <= n; i++) {
if(a[i]-EPS >= 1.0) an = i;
if(b[i]-EPS >= 1.0) bn = i;
a[i] = max(0.0, a[i]-1);
b[i] = max(0.0, b[i]-1);
}
for(int i = 1; i <= an; i++) {
a[i] += a[i-1];
}
for(int i = 1; i <= bn; i++) {
b[i] += b[i-1];
}
double rez = 0;
for(int i = 1; i <= an; i++) {
int idx = bs(a, b, i, 1, bn);
rez = max(rez, b[idx]-i);
}
for(int i = 1; i <= bn; i++) {
int idx = bs(b, a, i, 1, an);
rez = max(rez, a[idx]-i);
}
cout << fixed << setprecision(4) << rez;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3736 KB |
Output is correct |
2 |
Correct |
0 ms |
3736 KB |
Output is correct |
3 |
Correct |
0 ms |
3736 KB |
Output is correct |
4 |
Correct |
0 ms |
3736 KB |
Output is correct |
5 |
Correct |
0 ms |
3736 KB |
Output is correct |
6 |
Correct |
0 ms |
3736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3736 KB |
Output is correct |
2 |
Correct |
0 ms |
3736 KB |
Output is correct |
3 |
Correct |
0 ms |
3736 KB |
Output is correct |
4 |
Correct |
0 ms |
3736 KB |
Output is correct |
5 |
Correct |
0 ms |
3736 KB |
Output is correct |
6 |
Correct |
0 ms |
3736 KB |
Output is correct |
7 |
Correct |
0 ms |
3736 KB |
Output is correct |
8 |
Correct |
0 ms |
3736 KB |
Output is correct |
9 |
Correct |
0 ms |
3736 KB |
Output is correct |
10 |
Correct |
0 ms |
3736 KB |
Output is correct |
11 |
Correct |
0 ms |
3736 KB |
Output is correct |
12 |
Correct |
0 ms |
3736 KB |
Output is correct |
13 |
Correct |
0 ms |
3736 KB |
Output is correct |
14 |
Correct |
0 ms |
3736 KB |
Output is correct |
15 |
Correct |
0 ms |
3736 KB |
Output is correct |
16 |
Correct |
0 ms |
3736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
3736 KB |
Output is correct |
2 |
Correct |
0 ms |
3736 KB |
Output is correct |
3 |
Correct |
0 ms |
3736 KB |
Output is correct |
4 |
Correct |
0 ms |
3736 KB |
Output is correct |
5 |
Correct |
0 ms |
3736 KB |
Output is correct |
6 |
Correct |
0 ms |
3736 KB |
Output is correct |
7 |
Correct |
0 ms |
3736 KB |
Output is correct |
8 |
Correct |
0 ms |
3736 KB |
Output is correct |
9 |
Correct |
0 ms |
3736 KB |
Output is correct |
10 |
Correct |
0 ms |
3736 KB |
Output is correct |
11 |
Correct |
0 ms |
3736 KB |
Output is correct |
12 |
Correct |
0 ms |
3736 KB |
Output is correct |
13 |
Correct |
0 ms |
3736 KB |
Output is correct |
14 |
Correct |
0 ms |
3736 KB |
Output is correct |
15 |
Correct |
0 ms |
3736 KB |
Output is correct |
16 |
Correct |
0 ms |
3736 KB |
Output is correct |
17 |
Correct |
123 ms |
3736 KB |
Output is correct |
18 |
Correct |
113 ms |
3736 KB |
Output is correct |
19 |
Correct |
109 ms |
3736 KB |
Output is correct |
20 |
Correct |
106 ms |
3736 KB |
Output is correct |
21 |
Correct |
113 ms |
3736 KB |
Output is correct |
22 |
Correct |
99 ms |
3736 KB |
Output is correct |
23 |
Correct |
106 ms |
3736 KB |
Output is correct |
24 |
Correct |
109 ms |
3736 KB |
Output is correct |
25 |
Correct |
103 ms |
3736 KB |
Output is correct |
26 |
Correct |
123 ms |
3736 KB |
Output is correct |