Submission #890625

#	Time	Username	Problem	Language	Result	Execution time	Memory
890625		Keys	Seesaw (JOI22_seesaw)	C++14	100 / 100	127 ms	24000 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long double db;
#define ar array
#define all(x) x.begin(), x.end()
#define pb push_back
#define sz(x) int(x.size())
#define endl '\n'
#define f first
#define s second
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = a; i >= b; i--)
#define trav(i, a) for (auto& i : a)
template <class T> istream &operator>>(istream& in, vector<T> &v) {trav(i, v) in >> i; return in;}

#ifdef LOCAL
#include "../../lib/debug.h"
#else
#define dbg(...)
#endif

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n; vi a(n); cin >> a; vi p = a; FOR(i, 1, n) p[i] += p[i - 1];
  auto baro = [&] (int l, int r) {
    return db(p[r] - (l ? p[l - 1] : 0)) / db(r - l + 1);
  };
  vector<pair<db, int>> c; c.pb({baro(0, n - 1), n});
  for (int i = 1; i < n; i++) {
    int lo = 0, hi = n - i;
    while (lo < hi) {
      int m = (lo + hi + 1) / 2;
      if (baro(m, m + i - 1) <= baro(0, n - 1)) lo = m;
      else hi = m - 1;
    }
    c.pb({baro(lo, lo + i - 1), i});
    if (lo + 1 <= n - i) c.pb({baro(lo + 1, lo + i), i});
  }
  sort(all(c));
  vi vis(n + 1, 0); int amt = 0;
  int j = 0;
  db ans = 1e18;
  dbg(c);
  FOR(i, 0, sz(c)) {
    while (j < sz(c) and amt != n) {
      if (!vis[c[j].s]) amt++;
      vis[c[j].s]++;
      j++;
    }
    if (amt == n) {
      ans = min(ans, c[j - 1].f - c[i].f);
      vis[c[i].s]--;
      if (!vis[c[i].s]) amt--;
    } else {
      break;
    }
  }
  cout << fixed << setprecision(10) << ans << endl;
}

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33