Submission #1160416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160416		sl1pzz	Sure Bet (CEOI17_sure)	C++20	100 / 100	92 ms	5212 KiB

sure

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

#define int long long
#define pb push_back
#define ew "\n"
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
#define len(x) (int)x.size()
#define eb emplace_back
#define turbo                       \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0);

const int maxn = 5e5 + 12;
const int mxx = 100100;
const int MOD = 1e9 + 7;
const int inf = 2e18 + 7;
const int HH = 1e2 + 70;

int n;
long double a[maxn], b[maxn];

void code()
{
  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(b + 1, b + n + 1);
  reverse(a + 1, a + n + 1);
  double rs = 0;
  vector<double> aa(n + 1, 0), bb(n + 1, 0);
  for (int i = 1; i <= n; i++)
  {
    aa[i] = aa[i - 1] + a[i];
    bb[i] = bb[i - 1] + b[i];
  }
  for (int md = 0; md <= 2 * n; md++)
  {
    int L = max(0ll, md - n);
    int R = min(md, n);
    if (L > R)
    {
      continue;
    }
    int l = L, r = R;
    int x = L;
    double cur = fabsl(aa[L] - bb[md - L]);
    while (l <= r)
    {
      int mid = (l + r) >> 1;
      double dif = aa[mid] - bb[md - mid];
      if (fabsl(dif) < cur)
      {
        cur = fabsl(dif);
        x = mid;
      }
      if (dif < 0)
      {
        l = mid + 1;
      }
      else
      {
        r = mid - 1;
      }
    }
    for (int to = max(L, x - 1); to <= min(R, x + 1); to++)
    {
      double v = min(aa[to], bb[md - to]) - md;
      rs = max(rs, v);
    }
  }
  cout << fixed << setprecision(4) << rs;
}

int32_t main()
{
  // freopen("248.in", "r", stdin);
  // freopen("248.out", "w", stdout);
  // turbo;
  int tt = 1, j = 1;
  // cin >> tt;
  while (tt--)
  {
    // cout << "Case " << j << ":" << ew;
    code();
    // j++;
  }
}

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