This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ld long double
const int maxn = 1e5 + 20;
ld res , sum[maxn] , a[maxn] , b[maxn];
void solve(int n)
{
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++)
sum[i] = sum[i - 1] + b[i];
ld s = 0;
for(int i = 1; i <= n; i++)
{
s += a[i];
int k = lower_bound(sum , sum + n + 1 , s) - sum;
if(k > n + 1)
k--;
res = max(res , min(sum[k] , s) - k - i);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
solve(n);
for(int i = 1; i <= n; i++)
swap(a[i] , b[i]);
solve(n);
cout << fixed << setprecision(4) << res << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |