Submission #570782

#TimeUsernameProblemLanguageResultExecution timeMemory
570782ShinSure Bet (CEOI17_sure)C++14
100 / 100
78 ms3532 KiB
#include <bits/stdc++.h> #define fi first #define se second #define mp make_pair #define all(x) x.begin(), x.end() using namespace std; template <class X, class Y> bool minimize(X &a, Y b) { if (a > b) return a = b, true; return false; } template <class X, class Y> bool maximize(X &a, Y b) { if (a < b) return a = b, true; return false; } const int N = 1e5 + 7; int n; double a[N]; double b[N]; double pre_a[N]; double pre_b[N]; double res; signed main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i ++) { cin >> a[i] >> b[i]; } sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); reverse(a + 1, a + n + 1); reverse(b + 1, b + n + 1); for (int i = 1; i <= n; i ++) { pre_a[i] = pre_a[i - 1] + a[i]; pre_b[i] = pre_b[i - 1] + b[i]; } for (int i = 1, j = 1; i <= n; i ++) { while (j < n && pre_a[j + 1] <= pre_b[i]) { j ++; } if (pre_b[i] < pre_a[j]) { maximize(res, pre_b[i] - i - j); } else { maximize(res, pre_a[j] - i - j); if (j < n) maximize(res, pre_b[i] - i - j - 1); } } cout << fixed << setprecision(4) << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...