Submission #1027224

#TimeUsernameProblemLanguageResultExecution timeMemory
1027224vjudge1Sure Bet (CEOI17_sure)C++17
100 / 100
53 ms1996 KiB
#include<bits/stdc++.h> #define int long long #define fi first #define se second #define pb push_back #define ii pair<int, int> #define sz(v) (int)v.size() #define all(v) v.begin(), v.end() using namespace std; const int N=1e5+5, mod = 1e9+7, inf = 1e18; int n; double a[N], b[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i=1; i<=n; i++) { cin >> a[i] >> b[i]; a[i]-=1.0; b[i]-=1.0; } sort(a+1, a+n+1, greater<double>()); sort(b+1, b+n+1, greater<double>()); for (int i=1; i<=n; i++) { a[i] += a[i-1]; b[i] += b[i-1]; } double res = (double) -inf; for (int na = 0; na<=n; na++) { int lo = 0, hi = n, ans = -1; while(lo<=hi) { int mid = (lo+hi)>>1; if(a[na] - mid >= b[mid] - na) { ans = mid; lo = mid+1; } else { hi = mid-1; } } if(ans != -1) res = max(res, b[ans]-na); if(ans<n) res = max(res, a[na]-ans-1); } cout << fixed << setprecision(4) << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...