oj.uz

Submission #890625

# Submission time Handle Problem Language Result Execution time Memory
890625 2023-12-21T16:54:17 Z Keys Seesaw (JOI22_seesaw) C++14
100 / 100
 127 ms 24000 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 113 ms 23272 KB Output is correct
13 Correct 112 ms 23740 KB Output is correct
14 Correct 127 ms 24000 KB Output is correct
15 Correct 112 ms 23744 KB Output is correct
16 Correct 111 ms 22972 KB Output is correct