Submission #1127038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127038		duckindog	Seesaw (JOI22_seesaw)	C++20	34 / 100	2098 ms	75892 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

#define double long double

const int N = 2'000 + 10;
const double MAX = 1e9;

int n;
int a[N];
long long pref[N];
inline long long sum(int l, int r) { return pref[r] - pref[l - 1]; }
inline double cal(int l, int r) { return (double)sum(l, r) / (r - l + 1); }

int way[N][N];
double f[N][N];
pair<int, int> par[N][N];
bool mk[N][N];

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

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

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

  for (int i = 1; i <= n; ++i) { 
    for (int j = 1; j <= n; ++j) f[i][j] = MAX;
  }

  f[1][n] = cal(1, n);
  using TP = tuple<double, int, int>;
  priority_queue<TP, vector<TP>, greater<>> q;
  
  double answer = MAX;
  auto go = [&](int x, int y) { 
    if (!x && !y) return;
    double mi = MAX;
    while (x != y) { 
      f[x][y] = max(f[x][y], cal(x, y));
      if (!mk[x][y]) q.emplace(cal(x, y), x, y), mk[x][y] = true;
      mi = min(mi, cal(x, y));

      int nX = (!way[x][y] ? x : x + 1), nY = (!way[x][y] ? y - 1 : y);
      f[nX][nY] = f[x][y];
      par[nX][nY] = {x, y};

      tie(x, y) = {nX, nY};
    } 
    f[x][y] = max(f[x][y], cal(x, y));
    if (!mk[x][y]) q.emplace(cal(x, y), x, y), mk[x][y] = true;
    mi = min(mi, cal(x, y));
    
    answer = min(answer, f[x][y] - min(cal(1, n), get<0>(q.top())));
  };
  
  go(1, n);
  while (q.size()) { 
    auto [d, i, j] = q.top(); q.pop();
    auto [x, y] = par[i][j];
    if (way[x][y]) continue;
    way[x][y] = 1;
    go(x, y);
  }
  
  cout << setprecision(9) << fixed << answer << "\n";
}

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