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 <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <string>
#include <set>
#include <vector>
#include <iostream>
using namespace std;
void output(double p1, double p2)
{
if(p1 < 0 ||p2<0)
printf("%.4lf", (double)(0));
else
printf("%.4lf", (double)(min(p1, p2)));
}
long double ternarySearch(vector<long double>&
prefSum2, int minK, int maxK, long double deficit, long double profPure1)
{
int r = maxK, l = minK;
while(r-l > 3)
{
int m1 = l + (r-l)/3;
int m2 = r - (r-l)/3;
long double part1fM1 = profPure1 - m1-1;
long double part2fM1 = prefSum2[m1] + deficit - m1-1;
long double fm1 = min(part1fM1, part2fM1);
long double part1fM2 = profPure1 - m2-1;
long double part2fM2 = prefSum2[m2] + deficit - m2- 1;
long double fm2 = min(part1fM2, part2fM2);
if(fm1 < fm2)
{
l = m1;
}
else
{
r = m2;
}
}
long double bestVal = 0;
for(int i = l; i<= r; ++i)
{
long double part1 = profPure1 - i-1;
long double part2 = prefSum2[i] + deficit - i-1;
long double f =min(part1, part2);
if(f > bestVal)
bestVal = f;
}
return bestVal;
}
int main()
{
int n; cin>>n;
vector<long double> odds1(n), odds2(n);
for(int i = 0; i<n; ++i)
{
cin>>odds1[i]>>odds2[i];
}
sort(odds1.rbegin(), odds1.rend());
sort(odds2.rbegin(), odds2.rend());
vector<long double> prefSum1(n);
vector<long double> prefSum2(n);
prefSum1[0] = odds1[0];
prefSum2[0] = odds2[0];
for(int i =1; i<n; ++i)
{
prefSum1[i] = prefSum1[i-1]+odds1[i];
prefSum2[i] = prefSum2[i-1]+ odds2[i];
}
long double bestSureProf = 0;
for(int i = 0; i<n; ++i)
{
long double best = ternarySearch(prefSum2, 0, n-1, -i-1, prefSum1[i]-i-1);
if(best > bestSureProf)
bestSureProf = best;
}
output(bestSureProf, bestSureProf);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |