Submission #570775

#	Time	Username	Problem	Language	Result	Execution time	Memory
570775		Shin	Sure Bet (CEOI17_sure)	C++14	100 / 100	90 ms	3524 KiB

sure

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 1e5 + 7;

int n;
int f[N];
double a[N];
double b[N];
double pre_a[N];
double pre_b[N];
double res;

void backtrack(int i) {
  if (i > n) {
    int cur = 0;
    double l = 0, r = 0;
    for (int j = 1; j <= n; j ++) {
      if (f[j] == 1) {
        cur --;
        l += a[j];
      } else
      if (f[j] == 2) {
        cur --;
        r += b[j];
      } else
      if (f[j] != 0) {
        cur -= 2;
        l += a[j];
        r += b[j];
      }
    }
    maximize(res, min(r, l) + cur);
    return;
  }
  for (int j = 0; j < 4; j ++) {
    f[i] = j;
    backtrack(i + 1);
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  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(a + 1, a + n + 1);
  reverse(b + 1, b + n + 1);
  for (int i = 1; i <= n; i ++) {
    pre_a[i] = pre_a[i - 1] + a[i];
    pre_b[i] = pre_b[i - 1] + b[i];
  }
  if (n <= 10) {
    backtrack(1);
  } else {
    for (int i = 1, j = 1; i <= n; i ++) {
      while (j < n && pre_a[j + 1] <= pre_b[i]) {
        j ++;
      }
      if (pre_b[i] < pre_a[j]) {  
        maximize(res, pre_b[i] - i - j);
      } else {
        maximize(res, pre_a[j] - i - j);
        if (j < n) maximize(res, pre_b[i] - i - j - 1);
      }
    }
  }

  cout << fixed << setprecision(4) << res;
  return 0;
}

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