Submission #1127017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127017		duckindog	Seesaw (JOI22_seesaw)	C++20	0 / 100	0 ms	320 KiB

seesaw

#include <bits/stdc++.h>

using namespace std;

#define double long double

const int N = 2'000 + 10;
int n;
int a[N];
long long pref[N];
inline long long sum(int l, int r) { return pref[r] - pref[l - 1]; }

int way[N][N];
double f[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];

  double answer = 1e9;
  for (int l = 1; l <= n; ++l) { 
    for (int r = l; r <= n; ++r) {
      double mi = 1.0 * sum(l, r) / (r - l + 1);

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

      f[1][n] = 1.0 * sum(1, n) / n;
      for (int i = 1; i <= n; ++i) { 
        for (int j = n; j > i; --j) { 
          if ((double) sum(i, j) / (j - i + 1) < mi || f[i][j] == 1e9) continue;
          f[i][j] = max(f[i][j], (double) sum(i, j) / (j - i + 1));
          f[i + 1][j] = min(f[i + 1][j], f[i][j]);
          f[i][j - 1] = min(f[i][j - 1], f[i][j]);
        }
      }
      
      for (int i = 1; i <= n; ++i) answer = min(answer, f[i][i] - mi);
    }
  }

  cout << setprecision(10) << fixed << answer << "\n";
}

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