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 vi vector<double>
#define pb push_back
#define INF 1e9+7
int n;
vi a, b;
int main(){
cin>>n;
//cin.tie(0); //random_device dev;
//mt19937 rng(dev());
//uniform_int_distribution<std::mt19937::result_type> dist6(5,6);
//srand((unsigned)time(0));
//int i;
//i=(rand()%2)+5;
a.pb(INF); b.pb(INF);
for(int i=1; i<=n; i++){
double x,y;
cin>>x>>y;
a.pb(x);
b.pb(y);
}
sort(a.begin(), a.end(), greater<double>());
sort(b.begin(), b.end(), greater<double>());
//for(int i=1; i<=n; i++) cout<<a[i]<<" ";cout<<endl;
a[0]=0; b[0]=0;
for(int i=1; i<=n; i++){
a[i]+=a[i-1];
}
for(int i=1; i<=n; i++){
b[i]+=b[i-1];
}
double mx=0;
for(double x=0, y=0; x<=n && y<=n;){
if(a[x]<b[y]){
x++;
}
else y++;
mx=max(mx, min(a[x]-x-y, b[y]-x-y));
//cout<<x<<" "<<y<<" "<<min(a[x]-x-y, b[y]-x-y)<<endl;
}
printf("%.4lf",(double)mx);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |