Submission #1002093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002093		asdasdqwer	Sure Bet (CEOI17_sure)	C++14	100 / 100	137 ms	8276 KiB

sure

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ld long double
#define pii array<int,2>

vector<ld> prefSum(vector<ld> &a) {
  vector<ld> p(a.size());
  p[0] = a[0];
  for (int i=1;i<(int)a.size();i++) p[i]=p[i-1]+a[i];
  return p;
}

signed main() {
  int n;cin>>n;
  vector<ld> a(n), b(n);
  for (int i=0;i<n;i++) {
    cin>>a[i]>>b[i];
  }

  sort(a.begin(), a.end(), greater<ld>());
  sort(b.begin(), b.end(), greater<ld>());

  vector<ld> pa = prefSum(a), pb = prefSum(b);

  ld l = 0, r = 1e9;

  while (abs(l - r) >= 0.000001) {
    ld m = (l+r) / 2.0;
    bool pos = false;
    for (int i=0;i<n;i++) {
      ld wn = (pa[i] - (ld)(i+1)) - m;
      if (wn <= 0.0) continue;
      wn = floor(wn);
      int k = (int)wn;
      if (k <= 0) continue;
      k = min(k, n);
      ld pw = pb[k-1] - (ld)(i+1+k);
      if (pw >= m) {
        pos = true;
        break;
      }
    }

    if (pos) {
      l = m;
    }

    else {
      r = m;
    }
  }

  printf("%.4lf\n", (double)l);
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 40 / 40