#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef vector<double> vd;
vd a, b;
int main(){
iostream::sync_with_stdio(0); cin.tie(0);
int N; cin>>N;
for(int n=0; n<N; n++){
a.push_back(0);
b.push_back(0);
cin>>a[n]>>b[n];
}
sort(a.rbegin(), a.rend());
sort(b.rbegin(), b.rend());
double opt = 0.0;
double sm = 0.0;
vd pf; pf.assign(N, 0.0);
pf[0] = b[0];
for(int y=1; y<N; y++){
pf[y] = b[y]+pf[y-1];
}
for(int x=0; x<N; x++){
sm += a[x];
//here we need to find the least point where sm2>=sm, then the answer is either that or the highest point where sm>sm2
int l = 0, r = N-1;
while(l!=r){
int m = (l+r)/2;
if(pf[m]>=sm){
//sm2>sm
r = m;
} else {
l = m+1;
}
}
if(l>0)
opt = max(max(min(sm-(x+l+2), pf[l]-(x+l+2)), min(sm-(x+l+1), pf[l-1]-(x+l+1))), opt);
else
opt = max(opt, min(sm-(x+l+2), pf[l]-(x+l+2)));
}
printf("%.4lf", opt);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
360 KB |
Output is correct |
| 3 |
Correct |
2 ms |
416 KB |
Output is correct |
| 4 |
Correct |
2 ms |
472 KB |
Output is correct |
| 5 |
Correct |
2 ms |
476 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
360 KB |
Output is correct |
| 3 |
Correct |
2 ms |
416 KB |
Output is correct |
| 4 |
Correct |
2 ms |
472 KB |
Output is correct |
| 5 |
Correct |
2 ms |
476 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
2 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
764 KB |
Output is correct |
| 9 |
Correct |
2 ms |
764 KB |
Output is correct |
| 10 |
Correct |
2 ms |
764 KB |
Output is correct |
| 11 |
Correct |
2 ms |
764 KB |
Output is correct |
| 12 |
Correct |
3 ms |
812 KB |
Output is correct |
| 13 |
Correct |
3 ms |
812 KB |
Output is correct |
| 14 |
Correct |
3 ms |
936 KB |
Output is correct |
| 15 |
Correct |
3 ms |
936 KB |
Output is correct |
| 16 |
Correct |
3 ms |
944 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
360 KB |
Output is correct |
| 3 |
Correct |
2 ms |
416 KB |
Output is correct |
| 4 |
Correct |
2 ms |
472 KB |
Output is correct |
| 5 |
Correct |
2 ms |
476 KB |
Output is correct |
| 6 |
Correct |
2 ms |
588 KB |
Output is correct |
| 7 |
Correct |
2 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
764 KB |
Output is correct |
| 9 |
Correct |
2 ms |
764 KB |
Output is correct |
| 10 |
Correct |
2 ms |
764 KB |
Output is correct |
| 11 |
Correct |
2 ms |
764 KB |
Output is correct |
| 12 |
Correct |
3 ms |
812 KB |
Output is correct |
| 13 |
Correct |
3 ms |
812 KB |
Output is correct |
| 14 |
Correct |
3 ms |
936 KB |
Output is correct |
| 15 |
Correct |
3 ms |
936 KB |
Output is correct |
| 16 |
Correct |
3 ms |
944 KB |
Output is correct |
| 17 |
Correct |
110 ms |
4860 KB |
Output is correct |
| 18 |
Correct |
121 ms |
6220 KB |
Output is correct |
| 19 |
Correct |
115 ms |
7588 KB |
Output is correct |
| 20 |
Correct |
110 ms |
8956 KB |
Output is correct |
| 21 |
Correct |
153 ms |
10808 KB |
Output is correct |
| 22 |
Correct |
113 ms |
12080 KB |
Output is correct |
| 23 |
Correct |
171 ms |
13556 KB |
Output is correct |
| 24 |
Correct |
144 ms |
14824 KB |
Output is correct |
| 25 |
Correct |
111 ms |
16192 KB |
Output is correct |
| 26 |
Correct |
123 ms |
17932 KB |
Output is correct |
