Submission #310059

#TimeUsernameProblemLanguageResultExecution timeMemory
310059quocnguyen1012Sure Bet (CEOI17_sure)C++14
100 / 100
99 ms5240 KiB
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define ar array
#define eb emplace_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL
  int N; cin >> N;
  vector<double> a(N), b(N);
  vector<double> suma(N), sumb(N);
  for (int i = 0; i < N; ++i) {
    cin >> a[i] >> b[i];
  }

  sort(a.rbegin(), a.rend());
  sort(b.rbegin(), b.rend());

  for (int i = 0; i < N; ++i) {
    suma[i] = a[i];
    sumb[i] = b[i];
    if (i) suma[i] += suma[i - 1];
    if (i) sumb[i] += sumb[i - 1];
  }

  double res = 0;
  for (int i = 0, j = 0; i < N; ++i) {
    while (j < N - 1 && sumb[j] < suma[i])
      ++j;
    res = max(res, min(suma[i], sumb[j]) - i - j - 2);
  }

  for (int i = 0, j = 0; i < N; ++i) {
    while (j < N - 1 && suma[j] < sumb[i])
      ++j;
    res = max(res, min(sumb[i], suma[j]) - i - j - 2);
  }
  cout << fixed << setprecision(4) << res;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...