Submission #468670

#TimeUsernameProblemLanguageResultExecution timeMemory
468670paga2004Sure Bet (CEOI17_sure)C++14
100 / 100
99 ms4716 KiB
#include <bits/stdc++.h>

#define int long long

using namespace std;

#ifdef LOCAL
#define dbg(x) cerr << x << "\n";
#else
#define dbg(x)
#endif

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<double> a(n), b(n), prefixa(n), prefixb(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());

  prefixa[0] = a[0];
  prefixb[0] = b[0];

  for (int i = 1; i < n; i++) {
    prefixa[i] = prefixa[i - 1] + a[i];
    prefixb[i] = prefixb[i - 1] + b[i];
  }

  double best = 0;

  int pa = 0;
  int pb = 0;
  while (pa < n && pb < n) {
    double profita = prefixa[pa] - pa - pb - 2;
    double profitb = prefixb[pb] - pa - pb - 2;
    dbg(profita);
    dbg(profitb);
    best = max(min(profita, profitb), best);
    if (profita < profitb) {
      pa++;
    } else {
      pb++;
    }
  }
  printf("%.4lf\n", (double)best);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...