Submission #445737

#TimeUsernameProblemLanguageResultExecution timeMemory
445737Nima_NaderiSure Bet (CEOI17_sure)C++14
100 / 100
219 ms14576 KiB
///In the name of GOD //#pragma GCC optimize("O2") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MXN = 3e5 + 10; const ld EPS = 1e-9; ll n; ld A[MXN], B[MXN], psa[MXN], psb[MXN], ans; ld Cal(ll x, ll y){ return min(psa[x], psb[y]) - x - y; } ld Calc(){ for(int i = 1; i <= n; i ++){ psa[i] = psa[i - 1] + A[i]; psb[i] = psb[i - 1] + B[i]; } for(int i = 1; i <= n; i ++){ ll l = 0, r = n; ans = max(ans, Cal(i, l)); ans = max(ans, Cal(i, r)); while(r - l > 10){ ll tid1 = (l * 2 + r) / 3; ll tid2 = (l + r * 2) / 3; ld nw1 = Cal(i, tid1); ld nw2 = Cal(i, tid2); ans = max(ans, nw1); ans = max(ans, nw2); if(nw1 > nw2) r = tid2; else l = tid1; } for(int j = l; j <= r; j ++){ ans = max(ans, Cal(i, j)); } } return ans; } int main(){ ios::sync_with_stdio(0);cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i ++) cin >> A[i] >> B[i]; sort(A + 1, A + n + 1, greater<ld>()); sort(B + 1, B + n + 1, greater<ld>()); ans = max(ans, Calc()); swap(A, B); ans = max(ans, Calc()); cout << fixed << setprecision(4) << ans << '\n'; return 0; } /*! HE'S AN INSTIGATOR, ENEMY ELIMINATOR, AND WHEN HE KNOCKS YOU BETTER YOU BETTER LET HIM IN. */ //! N.N
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...