fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int n;
  8.     cin >> n;
  9.     vector<double> a(n), b(n);
  10.     for (int i = 0; i < n; i++) {
  11.         double t, r;
  12.         cin >> t >> r;
  13.         a[i] = t - 1;
  14.         b[i] = r - 1;
  15.     }
  16.     sort(a.rbegin(), a.rend());
  17.     sort(b.rbegin(), b.rend());
  18.     vector<double> A(n + 1), B(n + 1), G(n + 1);
  19.     for (int i = 1; i <= n; i++) A[i] = A[i - 1] + a[i - 1];
  20.     for (int i = 1; i <= n; i++) B[i] = B[i - 1] + b[i - 1];
  21.     for (int i = 0; i <= n; i++) G[i] = B[i] + i;
  22.     double ans = 0;
  23.     for (int s = 0; s <= n; s++) {
  24.         double F = A[s] + s;
  25.         int t0 = int(upper_bound(G.begin(), G.end(), F) - G.begin()) - 1;
  26.         if (t0 >= 0) ans = max(ans, B[t0] - s);
  27.         if (t0 + 1 <= n) ans = max(ans, A[s] - (t0 + 1));
  28.     }
  29.     cout << fixed << setprecision(4) << ans << "\n";
  30. }
  31.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5
stdout
copy 
0.5000
https://ideone.com/pAcPOE
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!