Submission #1128817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128817		zNatsumi	Seesaw (JOI22_seesaw)	C++20	100 / 100	359 ms	62880 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

using tp = tuple<double, int, int>;

const int N = 2e5 + 5;
const long long INF = 1e18;

int n, a[N], pref[N];
double res = INF;
map<int, bool> mrk[N];
priority_queue<tp, vector<tp>, greater<>> pq;
multiset<double> s;

double MID(int l, int r){ return (double)(pref[r] - pref[l - 1]) / (r - l + 1); }

void init(){
  for(int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i];

  for(int i = n; i >= 1; i--){
    int l = 1, r = n - i + 1, pos1 = -1;

    while(l <= r){
      int mid = (l + r)/2;
      if(MID(mid, mid + i - 1) <= MID(1, n)) l = (pos1 = mid) + 1;
      else r = mid - 1;
    }
    int pos2 = pos1 + 1;
    if(1 <= pos1 && pos1 <= n - i + 1){
      mrk[pos1][pos1 + i - 1] = true;
      pq.emplace(MID(pos1, pos1 + i - 1), pos1, pos1 + i - 1);
      s.insert(MID(pos1, pos1 + i - 1));
    }

    if(1 <= pos2 && pos2 <= n - i + 1){
      mrk[pos2][pos2 + i - 1] = true;
      pq.emplace(MID(pos2, pos2 + i - 1), pos2, pos2 + i - 1);
    }
  }
}
void solve(){
  init();
  while(pq.size()){
    auto [mn, l, r] = pq.top(); pq.pop();

    res = min(res, *s.rbegin() - mn);

    s.erase(s.find(mn));
    if(mrk[l + 1].find(r + 1) == mrk[l + 1].end() || (l == 1 && r == n)) break;
    s.insert(MID(l + 1, r + 1));
  }
  cout << setprecision(12) << fixed << res << "\n";
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  solve();

  return 0;
}

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