Submission #924687

#TimeUsernameProblemLanguageResultExecution timeMemory
924687NK_Sure Bet (CEOI17_sure)C++17
0 / 100
0 ms348 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define sz(x) int(x.size()) using db = double; using ll = long long; template<class T> using V = vector<T>; using vl = V<ll>; const ll MUL = ll(1e4); int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; vl A(N), B(N); for(int i = 0; i < N; i++) { double x, y; cin >> x >> y; A[i] = ll(db(MUL) * x), B[i] = ll(db(MUL) * y); } sort(rbegin(A), rend(A)); sort(rbegin(B), rend(B)); for(int i = 1; i < N; i++) A[i] += A[i - 1]; for(int i = 1; i < N; i++) B[i] += B[i - 1]; // for(auto& x : A) cout << x << " "; // cout << endl; // for(auto& x : B) cout << x << " "; // cout << endl; ll ans = 0; for(int x = 2; x <= 2 * N; x++) { // cout << x << " ===> " << endl; // take x odds auto F = [&](int i) { if (i <= 0) return -1LL; if (x - i <= 0) return -1LL; return min(A[i - 1] - x * 1LL * MUL, B[x - 1 - i] - x * 1LL * MUL); }; int lo = max(1, x - N), hi = min(x - 1, N); while(lo < hi) { int mid = (lo + hi + 1) / 2; if (A[mid - 1] < B[x - 1 - mid]) lo = mid; else hi = mid - 1; } ans = max(ans, F(lo)); ans = max(ans, F(lo - 1)); // maximize min_{1 <= i <= x}(A[i - 1] - x, B[x - i] - x) } ll ansr = ans % MUL, ansi = (ans - ansr) / MUL; db ANS = ansi + (ansr / db(MUL)); printf("%.4lf", ANS); exit(0-0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...