Submission #796719

#TimeUsernameProblemLanguageResultExecution timeMemory
796719acatmeowmeowSure Bet (CEOI17_sure)C++11
100 / 100
88 ms4384 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long const int N = 1e5; int n; double f[N + 5], se[N + 5], prefix[N + 5]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) cin >> f[i] >> se[i]; sort(f + 1, f + n + 1, greater<double>()); sort(se + 1, se + n + 1, greater<double>()); double seValue = se[1]; for (int i = 1; i <= n; i++, seValue += se[i]) prefix[i] = max(prefix[i - 1], seValue - (double)i); double l = -1e9, r = 1e9, ans = -1e9; const double eps = 1e-6; while (r - l > eps) { double m = (l + r)/2.0, fValue = 0.0; bool valid = false; for (int i = 0; i <= n; i++) { fValue += f[i]; long long rem = min((long long)n, (long long)floor(fValue - m) - i); if(rem < 0) continue; valid |= prefix[rem] - (double)i > m || abs(prefix[rem] - (double)i - m) < eps; } if (valid) ans = m, l = m; else r = m; } cout << fixed << setprecision(4) << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...