Submission #1127062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127062		zNatsumi	Seesaw (JOI22_seesaw)	C++20	67 / 100	2105 ms	299816 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

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

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

int n, a[N];

namespace sub3{
  long 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] = (long 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<long 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";
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
  
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];

  sub3::solve();

  return 0;
}

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