Submission #1128815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128815		zNatsumi	Seesaw (JOI22_seesaw)	C++20	100 / 100	369 ms	63044 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

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

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

int n, a[N];

namespace sub3{
  double value[5005][5005], res = INF;

  void solve(){
    for(int i = 1; i <= n; i++){
      int sum = 0;
      for(int j = i; j <= n; j++){
        sum += a[j];
        value[i][j] = (double)sum / (j - i + 1);
      }
    }
    priority_queue<tp, vector<tp>, greater<>> pq;
    for(int i = 1; i <= n; i++)
      for(int j = i; j <= n; j++) pq.push({value[i][j], i, j});
    multiset<double> s;
    for(int i = 1; i <= n; i++) s.insert(value[1][i]);

    while(pq.size()){
      auto [mn, l, r] = pq.top(); pq.pop();

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

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

namespace sub4{
  int 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();
    cout << setprecision(12) << fixed;
    cerr << setprecision(12) << fixed;

    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 << res << "\n";
  }
}

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

//  freopen("test.inp", "r", stdin);
//  freopen("test.out", "w", stdout);

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

  sub4::solve();

  return 0;
}

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