Submission #580968

#TimeUsernameProblemLanguageResultExecution timeMemory
580968webSure Bet (CEOI17_sure)C++17
100 / 100
241 ms8364 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...