#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
// #define endl "\n"
int n;
main(){
/*ifstream cin(".in");
ofstream cout(".out");*/
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
float a[n] = {}, b[n] = {};
for (int i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
sort(a, a + n, greater<float>());
sort(b, b + n, greater<float>());
float pre[n] = {b[0]};
for (int i = 1; i < n; i++){
pre[i] = pre[i - 1] + b[i];
}
float left = 0, res = (float)0;
for (int i = 0; i < n; i++){
left += a[i];
int l = 0, r = n - 1, ans = n - 1;
while (l <= r){
int mid = (l + r) / 2;
float right = pre[mid];
if (right >= left){
ans = mid;
r = mid - 1;
}else{
l = mid + 1;
}
}
res = max(res, (float)min(pre[ans] - (float)ans - (float)i - 2.0, (float)left - (float)ans - (float)i - 2.0));
// cout << (float)left - (float)ans - (float)i - 2.0 << endl;
if (ans){
ans -= 1.0;
res = max(res, (float)min(pre[ans] - (float)ans - (float)i - 2.0, (float)left - (float)ans - (float)i - 2.0));
}
}
cout << res << endl;
}
Compilation message (stderr)
sure.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
10 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |