Submission #583323

#	Time	Username	Problem	Language	Result	Execution time	Memory
583323		600Mihnea	Sure Bet (CEOI17_sure)	C++17	100 / 100	100 ms	8328 KiB

sure

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  ///freopen ("input.txt", "r", stdin);

  int n;
  cin >> n;
  vector<ld> s1(n + 1, 0), s2(n + 1, 0);
  {
    vector<ld> a(n), b(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i] >> b[i];
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    for (int i = 0; i < n; i++) {
      s1[i + 1] = s1[i] + a[i];
      s2[i + 1] = s2[i] + b[i];
    }
  }

  ld sol = 0;

  for (int iter = 0; iter < 2; iter++) {
    swap(s1, s2);
    vector<ld> pref(n + 1);
    for (int i = 0; i <= n; i++) {
      pref[i] = s2[i] - i;
      if (i - 1 >= 0) {
        pref[i] = max(pref[i - 1], pref[i]);
      }
    }
    int t2 = 0;
    for (int t1 = 0; t1 <= n; t1++) {
      while (t2 + 1 <= n && s2[t2 + 1] <= s1[t1]) {
        t2++;
      }
      if (s2[t2] <= s1[t1]) {
        sol = max(sol, pref[t2] - t1);
      }
    }
  }
  cout << fixed << setprecision(4) << sol << "\n";
}

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